题目描述
给出一个长度为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]≠b[i](1<=i<=N) 注：gcd(x1,x2,…,xn)为x1, x2, …, xn的最大公约数。 输出答案对1,000,000,007取模的值。
输入
第一行包含3个整数，N，M，K。 第二行包含N个整数：a[1], a[2], …, a[N]。
输出
输出M个整数到一行，第i个整数为当d=i时满足条件的不同数列{b[n]}的数目mod 1,000,000,007的值。
样例输入
3 3 3
3 3 3
样例输出
7 1 0
题解
数学+容斥
老套路了，先处理出 $\gcd$ 为 $d$ 的倍数的方案数：
预处理出 $\{a[n]\}$ 中 $d$ 的倍数的数目 $c[d]$ ，那么 $d$ 的倍数中需要有 $n-k$ 个与 $\{a[n]\}$ 相同，有 $C_{c[d]}^{n-k}$ 种方案。
其余 $c[d]-n+k$ 个 $d$ 的倍数每个都有 $\lfloor\frac md\rfloor-1$ 种方案，因为 $d$ 的倍数总共有 $\lfloor\frac md\rfloor$ 个，减去不能等于原序列的1个。
剩下 $n-c[d]$ 个非 $d$ 的倍数的每个有 $\lfloor\frac md\rfloor$ 种方案。
因此 $\gcd$ 为 $d$ 的倍数的方案数就是 $C_{c[d]}^{n-k}\times(\lfloor\frac md\rfloor -1)^{c[d]-n+k}\times(\lfloor\frac md\rfloor)^{n-c[d]}$ 。
然后这个答案需要容斥一下，减去 $d$ 的2以上倍数的答案。
即 $ans[d]=C_{c[d]}^{n-k}\times(\lfloor\frac md\rfloor -1)^{c[d]-n+k}\times(\lfloor\frac md\rfloor)^{n-c[d]}-\sum\limits_{i=2}^{\lfloor\frac md\rfloor}ans[i\times d]$ 。
从大到小循环 $d$ ，后面的 $ans$ 已经求出，直接减掉即可，不需要莫比乌斯反演。
由于数的范围只有 $m=300000$ ，因此每一步都可以调和级数预处理。
时间复杂度 $O(n\log n)$
#include <cstdio>
#define N 300010
#define mod 1000000007
typedef long long ll;
int a[N] , v[N] , c[N];
ll fac[N] , ans[N];
inline ll pow(ll x , int y)
{
ll ans = 1;
while(y)
{
if(y & 1) ans = ans * x % mod;
x = x * x % mod , y >>= 1;
}
return ans;
}
int main()
{
int n , m , k , i , j;
scanf("%d%d%d" , &n , &m , &k) , k = n - k;
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , v[a[i]] ++ ;
for(i = 1 ; i <= m ; i ++ )
for(j = 1 ; i * j <= m ; j ++ )
c[i] += v[i * j];
fac[0] = 1;
for(i = 1 ; i <= n ; i ++ ) fac[i] = fac[i - 1] * i % mod;
for(i = m ; i ; i -- )
{
if(c[i] >= k) ans[i] = fac[c[i]] * pow(fac[k] , mod - 2) % mod * pow(fac[c[i] - k] , mod - 2) % mod * pow(m / i - 1 , c[i] - k) % mod * pow(m / i , n - c[i]) % mod;
for(j = 2 ; i * j <= m ; j ++ ) ans[i] = (ans[i] - ans[i * j] + mod) % mod;
}
for(i = 1 ; i < m ; i ++ ) printf("%lld " , ans[i]);
printf("%lld\n" , ans[m]);
return 0;
}
