BZOJ4305 数列的GCD

也许更好的阅读体验

$Description$Description

$Solution$Solution

这里就不用 $N,M$N,M，还是 $n,m$n,m写的习惯些
直接计算一个方案是十分不方便的
所以考虑容斥
设 $g\left(d\right)$g(d)表示 $d\mid gcd$d ∣ gcd的方案数
设 $a$a中有 $cnt$cnt个数是 $d$d的倍数
那么有
$g\left(d\right)={\left(\frac{m}{d}\right)}^{n-cnt}\left(\begin{array}{c}cnt\\ n-k\end{array}\right){(\frac{m}{d}-1)}^{k-(n-cnt)}$g(d)=(dm​)n−cnt(cntn−k​)(dm​−1)k−(n−cnt)

${\left(\frac{m}{d}\right)}^{n-cnt}$(dm​)n−cnt表示有 $n-cnt$n−cnt个数是必须修改的，每个有 $\frac{m}{d}$dm​种数选择

那么还剩 $k-(n-cnt)$k−(n−cnt)个数必须要修改，我们可将其写为 $cnt-(n-k)$cnt−(n−k)，这样就是等价于要选 $n-k$n−k个数出来

$\left(\begin{array}{c}cnt\\ n-k\end{array}\right){(\frac{m}{d}-1)}^{k-(n-cnt)}$(cntn−k​)(dm​−1)k−(n−cnt)表示将这 $cnt$cnt个数修改 $k-(n-cnt)$k−(n−cnt)个数，每个数因为自己本身是 $d$d的一个倍数，所以只有 $\frac{m}{d}$dm​种选择

设 $f\left(d\right)$f(d)表示 $gcd=d$gcd=d的方案数

然后可以考虑莫比乌斯反演
显然有
$\begin{array}{c}{\displaystyle g\left(n\right)=\sum _{n\mid d}f\left(d\right)}\end{array}$g(n)=n ∣ d∑​f(d)​
则根据莫比乌斯反演，有
$\begin{array}{c}{\displaystyle f\left(n\right)=\sum _{n\mid d}\mu \left(\frac{d}{n}\right)g\left(d\right)}\end{array}$f(n)=n ∣ d∑​μ(nd​)g(d)​

当然，莫比乌斯反演什么的是不可能莫比乌斯反演的
直接容斥就可以啦
$\begin{array}{c}{\displaystyle f\left(n\right)=g\left(n\right)-\sum _{n\mid d}f\left(d\right)}\end{array}$f(n)=g(n)−n∣d∑​f(d)​
从大到小枚举 $d$d，直接计算即可

$Code$Code

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年08月23日 星期五 08时14分25秒 *******************************/
#include <cstdio>
#include <fstream>
#define ll long long
using namespace std;
const int maxn = 300005;
const int mod = 1000000007;
//{{{cin
struct IO{
	template<typename T>
	IO & operator>>(T&res){
		res=0;
		bool flag=false;
		char ch;
		while((ch=getchar())>'9'||ch<'0')	 flag|=ch=='-';
		while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
		if (flag)	 res=~res+1;
		return *this;
	}
}cin;
//}}}
int n,m,k;
int a[maxn],num[maxn];
ll fac[maxn],inv[maxn],f[maxn];
//{{{ksm
int ksm (int a,int b)
{
	a%=mod;
	int s=1;
	for (;b;b>>=1,a=1ll*a*a%mod)
		if (b&1)	s=1ll*s*a%mod;
	return s;
}
//}}}
inline ll C (int n,int m)
{
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
	cin>>n>>m>>k;
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for (int i=1;i<=n;++i)	cin>>a[i],++num[a[i]];
	for (int i=2;i<=n;++i)	fac[i]=1ll*fac[i-1]*i%mod;
	for (int i=2;i<=n;++i)	inv[i]=(-mod/i*inv[mod%i]%mod+mod)%mod;
	for (int i=2;i<=n;++i)	inv[i]=1ll*inv[i]*inv[i-1]%mod;
	for (int i=m;i>=1;--i){
		int cnt=0;
		for (int j=i;j<=m;j+=i)	cnt+=num[j];
		if (cnt-n+k<0)	f[i]=0;
		else	f[i]=C(cnt,n-k)*ksm(m/i-1,cnt-n+k)%mod*ksm(m/i,n-cnt)%mod;
		for (int j=i<<1;j<=m;j+=i)	f[i]=1ll*(f[i]-f[j]+mod)%mod;
	}
	for (int i=1;i<=m;++i)	printf("%lld ",f[i]);
	return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧