题解 b

考场上只会暴力 \(n^4\) DP，部分分还写炸了

但其实这个DP可以前缀和优化到 \(n^3\) ，我觉得没有这档部分分就没写

但其实是有这一档的，我没有看出来……

正解想不到

如果我们已知使选的所有数 \(i\) 都满足 \(i \mid gcd\) 的方案数，就可以容斥得到答案

所以先求有多少种选择方案使得选的所有数均为 \(i\) 的倍数的方案数

然后考虑这一步如何容斥

发现对于 \(i > \lfloor \frac{n}{2} \rfloor\) 上面求出来的结果就是答案，因为没有倍数可以让它算重

然后对于这个分界线左边的第一个数，我们可以减掉它的倍数的方案数（这些方案数一定是正确的）来得到它的正确方案数

于是这个分界线左移了一位

重复上述过程，就可以得到答案了

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 100010

#define ll long long

#define reg register int

//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

inline int read() {

	int ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

int n, m;

int a[25][N], maxn, sta[N<<2], top, vis2[25][N];

bool vis[N];

ll dp[25][N], ans;

const ll p=1e9+7;

int gcd(int a, int b) {return !b?a:gcd(b, a%b);}

namespace task1{

	void solve() {

		for (reg i=1; i<=n; ++i)

			for (reg j=1; j<=m; ++j)

				sta[++top]=a[i][j];

		sort(sta+1, sta+top+1);

		top=unique(sta+1, sta+top+1)-sta-1;

		for (reg i=1; i<=top; ++i) {

			vis[sta[i]]=1;

			for (reg j=1; j<=top; ++j)

				vis[gcd(sta[i], sta[j])]=1;

		}

		for (reg i=n; i; --i) {

			for (reg j=1; j<=maxn; ++j) if (vis[j]) {

				dp[i][j]=j;

				for (reg k=i+1; k<=n; ++k) {

					for (reg h=1; h<=m; ++h) {

						dp[i][j] = (dp[i][j]+dp[k][gcd(j, a[k][h])])%p;

					}

				}

			}

		}

		for (reg i=1; i<=n; ++i)

			for (reg j=1; j<=m; ++j)

				ans = (ans+dp[i][a[i][j]])%p;

		printf("%lld\n", ans);

		exit(0);

	}

}

namespace task2{

	void solve() {

		ll ans=0;

		for (int i=1; i<=m; ++i) ans=(ans+a[1][i])%p;

		printf("%lld\n", ans);

		exit(0);

	}

}

namespace task3{

	ll fac[N], inv[N], mic[N], ans;

	ll C(int n, int k) {if (n==k) return 1ll; return !k?1ll:fac[n]*inv[k]%p*inv[n-k]%p;}

	void solve() {

		fac[0]=fac[1]=1; inv[0]=inv[1]=1; mic[0]=1;

		for (int i=2; i<=n; ++i) fac[i]=fac[i-1]*i%p;

		for (int i=2; i<=n; ++i) inv[i]=(p-p/i)*inv[p%i]%p;

		for (int i=2; i<=n; ++i) inv[i]=inv[i-1]*inv[i]%p;

		for (int i=1; i<=n+1; ++i) mic[i]=mic[i-1]*m%p;

		for (int i=1; i<=n; ++i)

			for (int j=0; j<=n-i; ++j)

				ans = (ans+C(n-i, j)*mic[j+1]%p)%p;

		printf("%lld\n", ans*a[1][1]%p);

		exit(0);

	}

}

namespace task{

	ll cnt[25][N], met[N], ans;

	void solve() {

		for (int i=1; i<=n; ++i) {

			cnt[i][1]=m;

			for (int j=2; j<=maxn; ++j)

				for (int k=1; k*j<=maxn; ++k)

					cnt[i][j]+=vis2[i][k*j];

		}

		//cout<<"cnt: "; for (int i=1; i<=maxn; ++i) cout<<cnt[1][i]<<' '; cout<<endl;

		for (int i=1; i<=maxn; ++i) {

			met[i]=1;

			for (int j=1; j<=n; ++j)

				met[i]=met[i]*(cnt[j][i]+1)%p;

			--met[i];

		}

		//cout<<"met: "; for (int i=1; i<=maxn; ++i) cout<<met[i]<<' '; cout<<endl;

		for (int i=maxn; i; --i) {

			for (int j=2; i*j<=maxn; ++j) met[i]-=met[i*j];

			ans = (ans+met[i]*i)%p;

		}

		//cout<<"met: "; for (int i=1; i<=maxn; ++i) cout<<met[i]<<' '; cout<<endl;

		printf("%lld\n", ((ans%p)+p)%p);

		exit(0);

	}

}

signed main()

{

	bool same=1; int lst=0;

	n=read(); m=read();

	for (reg i=1; i<=n; ++i)

		for (reg j=1; j<=m; ++j) {

			a[i][j]=read();

			maxn=max(maxn, a[i][j]);

			++vis2[i][a[i][j]];

			if (!lst) lst=a[i][j];

			else if (lst!=a[i][j]) same=0;

		}

	//if (n==1) task2::solve();

	//else if (same) task3::solve();

	//else task1::solve();

	task::solve();

	return 0;

}

巴特西

题解 b

最新文章

热门文章