题目链接
HDU4675
思路
首先这道题难的地方就是组合数学的地方，另一部分可以用很简单的莫比乌斯反演来写。
我们来分析k个a[i]≠b[i]，这个条件
假设gcd(b[])=d,那么b中肯定全都是d的倍数，所以我们需要把a[]中所有非d的倍数变成d的倍数，然后如果超过k个，那么肯定无法只有k个不同，所以答案是0
如果不超过k个，那么我们还需要从d的倍数中挑选出k-(n-num[d])个。
所以最后
第一部分减一是因为他们是d的倍数，但是必须修改，所以要就少了一个因子。
得到这个式子之后，再用莫比乌斯反演得出
我们先预处理出F，需要用到逆元的前缀积与费马小定理求逆元。
然后组合数求出F(n),然后暴力枚举d即可得到f(n)答案。
代码实现
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int md = 1e9+7;
const int maxn = 3e5+10;
int a[maxn];
int mu[maxn];
int F[maxn];
bool vis[maxn];
int prime[maxn],cnt;
int num[maxn];
int inv[maxn];
int pre[maxn];
int sum[maxn];
int n,m,k;
void get_mu()
{
mu[1]=1;
for(int i=2;i<maxn;i++)
{
if(!vis[i])
{
prime[cnt++]=i;
mu[i]=-1;
}
for(int j=0;j<cnt&&i*prime[j]<maxn;j++)
{
vis[i*prime[j]]=true;
if(i%prime[j])
{
mu[i*prime[j]]=-mu[i];
}
else
{
mu[i*prime[j]]=0;
break;
}
}
}
}
int quick_pow(int a,int k)
{
int ans = 1;
while(k)
{
if(k&1)ans=(1ll*ans*a)%md;
k>>=1;
a=(1ll*a*a)%md;
}
return ans;
}
void get_inv()
{
inv[1]=1;
for(int i=2;i<maxn;i++)inv[i]=(1ll*inv[i-1]*quick_pow(i,md-2))%md;
}
void get_pre()
{
pre[0]=1;
pre[1]=1;
for(int i=2;i<maxn;i++)
{
pre[i]=(1ll*pre[i-1]*i)%md;
}
}
ll get_C(int up,int down)
{
if(up==0)return 1;
return (1ll*(1ll*pre[down]*quick_pow(pre[down-up],md-2))%md*inv[up])%md;
}
void get_F()
{
for(int i=1;i<=m;i++)
{
int p = n-num[i];
if(k-p<0)F[i]=0;
else F[i]=((1ll*get_C(k-p,num[i])*quick_pow((m/i-1),k-p))%md*quick_pow(m/i,p))%md;
}
}
int main()
{
get_mu();
get_pre();
get_inv();
while(~scanf("%d %d %d",&n,&m,&k))
{
for(int i=0;i<=m;i++)num[i]=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
int m = sqrt(a[i]);
for(int j=1;j<=m;j++)
{
if(a[i]%j==0)
{
num[j]++;
num[a[i]/j]++;
}
if(j*j==a[i])num[j]--;
}
}
get_F();
ll ans = 0;
for(int i=1;i<=m;i++)
{ ll ans = 0;
for(int j=1;i*j<=m;j++)
{
ans+=1ll*mu[j]*F[i*j];
ans=(ans%md+md)%md;
}
if(i==1)printf("%lld",ans);
else printf(" %lld",ans);
}
printf("\n");
}
}
|