题目大意
给出一个长度为$N$的数列$a[i]$，$1\le a[i]\le M(1\le i\le N)$。
现在问题是，对于$1$到$M$的每个整数$d$，有多少个不同的数列$b[1],b[2],\ldots,b[N]$，满足：
$(1)1\le b[i]\le M(1\le i\le N)$；
$(2)\gcd(b[1],b[2],\ldots,b[N])=d$；
$(3)$恰好有$K$个位置$i$使得$a[i]=b[i] (1\le i\le N)$。
输出答案对$1000000007$取模的值。
题目分析
因为有条件$2$，因此留下与修改成的数必须都是$d$的倍数。
先统计出$d$的倍数的数有$cnt$个。
我们需要从$cnt$个数中选出$n-k$个数保持其不变，方案数为$C_{cnt}^{n-k}$。
并使得其他的所有数变化并变化成$d$的倍数。
首先将其他的本来是$d$的倍数的数修改成其他$d$的倍数的数，共有$cnt-(n-k)$个数，有$\lfloor\frac md\rfloor-1$种修改方案，方案数为$(\lfloor\frac md\rfloor-1)^{cnt-(n-k)}$。
再将不是$d$的倍数的数修改为$d$的倍数，共有$n-cnt$个数，有$\lfloor\frac md\rfloor$种修改方案，方案数为$\lfloor\frac md\rfloor^{n-cnt}$。
将上述方案乘起来就是答案：
但不难发现，这会算多，因为这些数的最大公约数可能是$d$的倍数而不是$d$，因此“小容斥一波”得出解。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
const LL mod=1e9+7;
LL n,m,k,Hash[maxn],fac[maxn],inv[maxn],invf[maxn],f[maxn];
LL C(int n,int m) {
return fac[n]*invf[n-m]%mod*invf[m]%mod;
}
LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
return sum;
}
int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++)Hash[Get_Int()]++;
fac[0]=invf[0]=inv[1]=1;
for(int i=1; i<=n; i++) {
fac[i]=fac[i-1]*i%mod;
if(i!=1)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
invf[i]=invf[i-1]*inv[i]%mod;
}
for(int i=1; i<=m; i++) {
int cnt=0;
for(int j=1; (LL)i*j<=m; j++)cnt+=Hash[i*j];
if(cnt<n-k)continue;
f[i]=C(cnt,n-k)*Quick_Pow(m/i-1,cnt-(n-k))%mod*Quick_Pow(m/i,n-cnt)%mod;
}
for(int i=m; i>=1; i--)
for(int j=2; (LL)i*j<=m; j++)f[i]=(f[i]-f[i*j]+mod)%mod;
for(int i=1; i<=m; i++)printf("%d ",f[i]);
return 0;
}
|
