题解 P4491 【[HAOI2018]染色】
command_block
2019-04-30 11:07:33
广告 : [炫酷反演魔术](https://www.luogu.com.cn/blog/command-block/xuan-ku-fan-yan-mo-shu) & [多项式计数杂谈](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan)
二项式反演经典题。
设 $G[k]$ 表示有**恰好** $k$ 种颜色出现了 $S$ 次的方案数。
我们需要求出 $W[1...n]$ 即可解决问题,这个 $n=\min(M,N/S)$
一个`naive`的想法是 : 钦定$k$种颜色,每种强行染上$S$次。
剩下的颜色放任自流,随便怎么染。
得到 $\dbinom{m}{k}*\dfrac{n!}{(S!)^k(n-S*k)!}*(n-S*k)^{m-k}$
组合意义 : "选 $k$ 种颜色$\times$可重排列$\times$放任自流"
那么这个东西肯定不是 $G[k]$ ,也并不是所谓 "至少 $k$ 种颜色出现了 $S$ 次的方案数"
事实上,这是会重复计数的,但是仍然以优美的方式蕴含了 $G[k]$。
我们设其为 $F[k]$。
- 我们先从特殊情况来分析
假设有三种颜色 $a,b,c$
按照上式的组合思想:
1) 钦定 $a,b$ ,然后随便染,不幸的是 $c$ 也出现了 $S$ 次
2) 钦定 $a,c$ ,然后随便染,不幸的是 $b$ 也出现了 $S$ 次
很明显会把 $a,b,c$ 都恰好出现 $S$ 次的方案算重复,所以严格来讲这个式子并不能称之为方案数……
究竟算重多少次呢?
考虑有 $4$ 种颜色 $a,b,c,d$
那么 $G[4]$ 与 $F[3]$ 间的贡献关系是什么呢?
$G[4]$ 在 $F[3]$ 钦定 $\{a,b,c\}$,$\{a,b,d\}$,$\{a,c,d\}$,$\{b,c,d\}$ 的时候各被算重一次,那么算重了 $\dbinom{4}{3}$ 次。
类比至一般情况,得到 $F[k]=\sum\limits_{i=k}^{n}\dbinom{i}{k}*G[i]$
已知 $F$ 要求 $G$ ,不就是二项式反演的经典操作嘛!
反演可得 $G[k]=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}F[i]$
到现在复杂度还是 $O(n^2)$ 的,我们考虑把组合数拆开看看能否卷积:
$G[k]=\sum\limits_{i=k}^n(-1)^{i-k}\dfrac{i!}{k!(i-k)!}F[i]$
$G[k]*k!=\sum\limits_{i=k}^n\dfrac{(-1)^{i-k}}{(i-k)!}i!F[i]$
这可以明显地看到差卷积形式了。
设 $A[i]=i!*F[i],\ B[i]=\dfrac{(-1)^i}{i!}$
则有$G[k]=\frac{1}{k!}\sum\limits_{i=k}^nA[i]B[i-k]$
NTT计算差卷积即可,复杂度$O(N+n\log n)$。
**Code:**
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int _G=3,mod=1004535809,Maxn=135000,MaxNum=10000500;
ll powM(ll a,int t=mod-2){
ll ans=1;
while(t){
if(t&1)ans=ans*a%mod;
a=a*a%mod;t>>=1;
}return ans;
}
const int invG=powM(_G);
int tr[Maxn<<1];
void NTT(int *g,bool op,int n)
{
#define ull unsigned long long
static ull f[Maxn<<1],w[Maxn]={1};
for (int i=0;i<n;i++)f[i]=g[tr[i]];
for(int l=1;l<n;l<<=1){
ull tG=powM(op?_G:invG,(mod-1)/(l+l));
for (int i=1;i<l;i++)w[i]=w[i-1]*tG%mod;
for(int k=0;k<n;k+=l+l)
for(int p=0;p<l;p++){
int tt=w[p]*f[k|l|p]%mod;
f[k|l|p]=f[k|p]+mod-tt;
f[k|p]+=tt;
}
if (l==(1<<10))
for (int i=0;i<n;i++)f[i]%=mod;
}if (!op){
ull invn=powM(n);
for(int i=0;i<n;++i)
g[i]=f[i]%mod*invn%mod;
}else for(int i=0;i<n;++i)g[i]=f[i]%mod;
}
int n,m,S,lim,limNum;
ll w[Maxn],fac[MaxNum],ifac[MaxNum];
void Init()
{
limNum=max(n,m);fac[0]=1;
for (int i=1;i<=limNum;i++)
fac[i]=fac[i-1]*i%mod;
ifac[limNum]=powM(fac[limNum]);
for (int i=limNum;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
ll C(int n,int m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
inline ll clacF(int x){
return
C(m,x)*fac[n]%mod*
powM(ifac[S],x)%mod*ifac[n-S*x]%mod*
powM(m-x,n-S*x)%mod;
}
int A[Maxn<<1],B[Maxn<<1];
int main()
{
scanf("%d%d%d",&n,&m,&S);
lim=min(m,n/S);Init();
for (int i=0;i<=lim;i++){
A[i]=clacF(i)*fac[i]%mod;
B[i]=(i&1) ? mod-ifac[i] : ifac[i];
}reverse(A,A+lim+1);
for(n=1;n<lim+lim+2;n<<=1);
for (int i=0;i<n;i++)
tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(A,1,n);NTT(B,1,n);
for (int i=0;i<n;i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,0,n);reverse(A,A+lim+1);
ll ans=0;
for (int i=0,w;i<=lim;i++){
scanf("%d",&w);
ans=(ans+A[i]*ifac[i]%mod*w)%mod;
}printf("%lld",ans);
return 0;
}
```