bzoj 4305 数列的GCD

LINK：数列的GCD

题意：

给出一个长度为N的数列{a[n]}，1<=a[i]<=M(1<=i<=N)。

现在问题是，对于1到M的每个整数d，有多少个不同的数列b[1], b[2], ..., b[N]，满足：

(1)1<=b[i]<=M(1<=i<=N)；

(2)gcd(b[1], b[2], ..., b[N])=d；

(3)恰好有K个位置i使得\(a_i\neq b_i\)(1<=i<=N)

注：gcd(x1,x2,...,xn)为x1, x2, ..., xn的最大公约数。

输出答案对1,000,000,007取模的值。

我没能想出来这道题感觉有点虚。应该多思考一下的。

有K个位置恰好不相等 n-K个位置恰好相等设当前处理的gcd为d 那么a序列能和b序列刚好相等的数的个数为M.M为a序列中为d的倍数的个数。

那么有C(M,n-k)的方案剩下的方案考虑这M-n+k个位置只有\(\lfloor \frac{M}{d}\rfloor-1\)种可能。

这里注意是排列不是组合(我傻了想成这里运用隔板法了剩下的 n-M个位置就有\(\lfloor \frac{M}{d}\rfloor\)可能。

最后发现有不合法的情况可以发现不合法的情况为gcd为d的倍数所以此时把d的倍数的答案都减掉即可。

const int MAXN=300010;

int n,m,k;

int a[MAXN],vis[MAXN];

ll fac[MAXN],inv[MAXN],ans[MAXN];

inline ll ksm(ll b,int p){if(p<0)return 0;ll cnt=1;while(p){if(p&1)cnt=cnt*b%mod;b=b*b%mod;p=p>>1;}return cnt;}

inline ll C(int a,int b){if(a<b)return 0;return fac[a]*inv[b]%mod*inv[a-b]%mod;}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(m);get(k);fac[0]=1;k=n-k;

	rep(1,n,i)++vis[get(a[i])],fac[i]=fac[i-1]*i%mod;

	inv[n]=ksm(fac[n],mod-2);

	fep(n-1,0,i)inv[i]=inv[i+1]*(i+1)%mod;

	fep(m,1,i)

	{

		ll cnt=0,sum=vis[i];

		for(int j=2;j*i<=m;++j)cnt=(cnt+ans[j*i])%mod,sum+=vis[i*j];

		ans[i]=C(sum,k)*ksm(m/i-1,sum-k)%mod*ksm(m/i,n-sum)%mod;

		ans[i]=(ans[i]-cnt+mod)%mod;

	}

	rep(1,m,i)printf("%lld ",ans[i]);

	return 0;

}

巴特西

bzoj 4305 数列的GCD

最新文章

热门文章