题解 P4491 【[HAOI2018]染色】

2020-04-28 17:09:15



[HAOI2018]染色


题意:

有一个长度为 n 的序列,m 种颜色,给定一个S,每种染色方案的价值是 $$ W_{出现次数等于S的颜色总数} $$ 求对所有染色方案的价值和,答案对 1004535809 取模。

数据范围 : n <=1e7 , m <= 1e5 ,S <=150


题解:

定义状态 f[i] 表示至少出现了 i 种颜色出现次数等于 S 的方案数, g[i] 表示恰好出现了i 种......

那么 f 的转移方程为 : $$ f[i]=C{i,m} * \frac{n!}{(n-i*S)! *(S!)^i} * (m-i)^{n-S*i} $$ 根据二项式反演 $$ g[i]=\sum_{j=i}^{lim} (-1)^{j-i} C(j,i) f[j] $$ 进一步转化为 $$ g[i]*i!=\sum_{j=i}^{lim} \frac{(-1)^{j-i}}{(j-i)!}f[j]* j! $$ 直接 NTT 在对 g 除一个 i! ,答案就是 $$ ans=\sum_{i=1}^{lim} g[i] * w[i] $$


代码:

#include<bits/stdc++.h>

using namespace std;

#define int long long

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    }
    while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
    return x*f;
}

const int maxn=1e7+5,maxm=4e5+5,mod=1004535809,G=3,Gi=334845270,N=1e7;

int n,m,s,f[maxm],cheng[maxn],inv[maxn],len=1,r[maxm],g[maxm],ans,W[maxm];

inline int power(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

inline int C(int n,int m){
    return cheng[n]*inv[m]%mod*inv[n-m]%mod;
}

inline void ntt(int *f,int len,int op){
    for(int i=0;i<len;i++) if(i<r[i]) swap(f[i],f[r[i]]);
    for(int i=1;i<len;i<<=1){
        int wn;if(op==1) wn=power(G,(mod-1)/(i<<1));else wn=power(Gi,(mod-1)/(i<<1));
        for(int j=0;j<len;j+=(i<<1)){
            int w=1;
            for(int k=0;k<i;k++,w=w*wn%mod){
                int nx=f[j+k],ny=f[i+j+k]*w%mod;
                f[j+k]=(nx+ny)%mod;
                f[i+j+k]=(nx-ny+mod)%mod;
            }
        }
    }
    if(op==1) return;
    int iv=power(len,mod-2);
    for(int i=0;i<len;i++) f[i]=f[i]*iv%mod;
}

signed main(){
    n=read();m=read();s=read();
    for(int i=0;i<=m;i++) W[i]=read();
    cheng[0]=1;for(int i=1;i<=N;i++) cheng[i]=cheng[i-1]*i%mod;
    inv[N]=power(cheng[N],mod-2);for(int i=N-1;i>=2;i--) inv[i]=inv[i+1]*(i+1)%mod;inv[0]=inv[1]=1;
    for(int i=0;i<=min(m,n/s);i++) f[i]= C(m,i)* cheng[n] %mod *inv[n-i*s] %mod *power( power( cheng[s],i ),mod-2 ) %mod * power( m-i , (n-i*s) ) %mod;
    for(int i=0;i<=min(m,n/s);i++) f[i]=f[i]*cheng[i]%mod;
    reverse(f,f+1+min(m,n/s));
    for(int i=0;i<=min(m,n/s);i++) g[i]=inv[i];
    for(int i=0;i<=min(m,n/s);i++) if(i&1) g[i]=-g[i];
    while(len<=(2*min(m,n/s))) len<<=1;
    for(int i=0;i<len;i++) r[i]=((r[i>>1]>>1)|((i&1)?(len>>1):0));
    ntt(f,len,1);ntt(g,len,1);for(int i=0;i<len;i++) f[i]=f[i]*g[i]%mod;
    ntt(f,len,-1);
    reverse(f,f+1+min(m,n/s));
    for(int i=0;i<=min(m,n/s);i++) f[i]=f[i]*inv[i]%mod*W[i]%mod;
    for(int i=0;i<=min(m,n/s);i++) ans=(ans+f[i])%mod;
    cout<<ans<<endl;
    return 0;
}