传送门:洛谷
解题思路:
写本题需要知道一个前置知识:
假设恰好选
k
k
k个条件的方案数为
f
(
k
)
f(k)
f(k);先钦定选
k
k
k个条件,其他条件无所谓的方案数为
g
(
k
)
g(k)
g(k)
那么存在这样的一个关系:
g
(
k
)
=
∑
i
=
k
n
C
i
k
f
(
i
)
g(k)=\sum_{i=k}^nC_{i}^kf(i)
g(k)=∑i=knCikf(i)
上述式子的含义是可以枚举实际上选了几个,然后再这
i
i
i个中选择
k
k
k个作为钦定的计算方案数.因为钦定这种方式是存在重复方案的
然后使用二项式反演可以实现钦定和恰好之间的转化.
经过二项式反演可以得到:
f
(
k
)
=
∑
i
=
k
n
C
i
k
∗
(
−
1
)
i
−
k
∗
g
(
i
)
f(k)=\sum_{i=k}^nC_{i}^{k}*(-1)^{i-k}*g(i)
f(k)=∑i=knCik∗(−1)i−k∗g(i).
对于本题来说,我们的
g
(
i
)
g(i)
g(i)其实很容易写出.设
g
(
i
)
g(i)
g(i)为恰好出现
i
i
i个的出现次数为
s
s
s的颜色的方案数.不难写出
g
(
i
)
=
C
m
i
A
n
s
∗
i
(
s
∗
i
)
!
∗
(
m
−
i
)
n
−
s
∗
i
g(i)=C_m^i\frac{A_n^{s*i}}{(s*i)!}*(m-i)^{n-s*i}
g(i)=Cmi(s∗i)!Ans∗i∗(m−i)n−s∗i
然后我们反演一下就得到了:
f
(
k
)
=
∑
i
=
k
n
C
i
k
(
−
1
)
i
−
k
g
(
i
)
f(k)=\sum_{i=k}^{n}C_{i}^{k}(-1)^{i-k}g(i)
f(k)=i=k∑nCik(−1)i−kg(i)
稍微化解一下就能得到:
f
(
k
)
∗
k
!
=
∑
i
=
k
n
g
(
i
)
∗
i
!
∗
(
−
1
)
i
−
k
(
i
−
k
)
!
f(k)*k!=\sum_{i=k}^ng(i)*i!*\frac{(-1)^{i-k}}{(i-k)!}
f(k)∗k!=i=k∑ng(i)∗i!∗(i−k)!(−1)i−k
然后我们设
G
(
i
)
=
g
(
i
)
∗
i
!
,
H
(
i
)
=
(
−
1
)
i
−
k
(
i
−
k
)
!
G(i)=g(i)*i!,H(i)=\frac{(-1)^{i-k}}{(i-k)!}
G(i)=g(i)∗i!,H(i)=(i−k)!(−1)i−k就能得到
F
(
k
)
=
∑
i
=
k
n
G
(
i
)
∗
H
(
i
−
k
)
F(k)=\sum_{i=k}^nG(i)*H(i-k)
F(k)=i=k∑nG(i)∗H(i−k)
我们使用经典套路将
G
G
G数组
r
e
v
e
r
s
e
reverse
reverse一下,就得到了
F
(
K
)
=
∑
i
=
k
n
G
(
n
−
i
)
∗
H
(
i
−
k
)
F(K)=\sum_{i=k}^nG(n-i)*H(i-k)
F(K)=i=k∑nG(n−i)∗H(i−k)
PS:需要注意的是此时翻转的n可以不为n,不熟悉的人可能会搞不清楚
然后这是一道很显然的卷积式子.此时我们使用
N
T
T
NTT
NTT卷一下即可.此时我们的的
f
(
k
)
f(k)
f(k)就是卷积完之后第
n
−
k
n-k
n−k项的系数.文章来源:https://www.toymoban.com/news/detail-725204.html
下面是具体的代码部分:文章来源地址https://www.toymoban.com/news/detail-725204.html
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline void print(__int128 x){
if(x<0) {putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
#define maxn 10001000
#define int long long
const int mod=1004535809;
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int qpow(int a,int b) {
int ans=1;
while(b) {
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
int rev[maxn];
void NTT(int *a,int n,int inv) {
for(int i=0;i<=n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int len=1;len<=(n>>1);len<<=1) {
int gn=qpow(inv==1?3:qpow(3,mod-2),(mod-1)/(len<<1));
for(int i=0;i<=n;i+=(len<<1)) {
int g0=1;
for(int j=0;j<=len-1;j++) {
int x=a[i+j],y=a[i+j+len]*g0%mod;
a[i+j]=(x+y)%mod;a[i+j+len]=((x-y)%mod+mod)%mod;
g0=g0*gn%mod;
}
}
}
}
int fac[maxn],in_fac[maxn];
void init(int limit) {
fac[0]=1;
for(int i=1;i<=limit;i++) {
fac[i]=fac[i-1]*i%mod;
}
in_fac[limit]=qpow(fac[limit],mod-2);
for(int i=limit-1;i>=0;i--) {
in_fac[i]=in_fac[i+1]*(i+1)%mod;
}
}
int C(int a,int b) {
return fac[a]*in_fac[b]%mod*in_fac[a-b]%mod;
}
int A(int a,int b) {
return fac[a]*in_fac[a-b]%mod;
}
int w[maxn];int g[maxn];int G[maxn],H[maxn];int F[maxn];
signed main() {
int n=read();int m=read();int s=read();
init(max(n,m));
for(int i=0;i<=m;i++) {
w[i]=read();
}
int k=min(m,n/s);
for(int i=0;i<=k;i++) {
g[i]=C(m,i)*A(n,s*i)%mod*qpow(in_fac[s],i)%mod*qpow(m-i,n-s*i)%mod;
}
for(int i=0;i<=k;i++) {
G[i]=g[i]*fac[i]%mod;
H[i]=((i&1?-1:1)*in_fac[i]%mod+mod)%mod;
}
reverse(G,G+k+1);
int limit=1,len=0;
while(limit<=k+k) limit<<=1,len++;
for(int i=0;i<=limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
NTT(G,limit,1);NTT(H,limit,1);
for(int i=0;i<=limit;i++) F[i]=G[i]*H[i]%mod;
NTT(F,limit,-1);
int inv=qpow(limit,mod-2);
for(int i=0;i<=limit;i++) {
F[i]=F[i]*inv%mod;
}
int ans=0;
for(int i=0;i<=k;i++) {
ans=(ans+F[k-i]*in_fac[i]%mod*w[i]%mod)%mod;
}
cout<<ans<<endl;
return 0;
}
到了这里,关于P4491 [HAOI2018] 染色的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!