[HAOI2018]染色

一股套路题的味道。。。

传送门

首先真正的颜色数$x=min(m,n/s)$。

考虑容斥：$f_i$表示至少有i种颜色出现S次的方案数。

那么
$$
f_i=C^i_mC^{i\times s}_n\times\frac{(i\times s)!}{(s!)^i}\times (m-i)^{n-i\times s}
$$
有至少就有恰好
$$
g_k=\sum_{i=k}^n(-1)^{i-k}C^k_if_i
$$

$$
=\sum_{i=k}^n(-1)^{i-k}\frac{i!}{(i-k)!k!}f_i
$$

$$
=\frac{1}{k!}\sum_{i=k}^n\frac{(-1)^{i-k}}{(i-k)!}\times f_i\times i!
$$

这是个套路啊。。。

设$A_i=\frac{(-1)^i}{i!}$，$B_i=f_i\times i!$。因为$i-k$和$i$的差是定值，把$B$反向，令$B’i=B{x-i}$。

就出现了$x-i+i-k=x-k$，那么令$A\times B’=C$

$C_k$就是恰好$x-k$种颜色的方案数，反过来，恰好$k$种颜色的方案数就是$C_{x-k}$。

NTT即可。

#include<cstdio>
#include<iostream>
using namespace std;
const int rt=3,mod=1004535809;
int w[100001],f[500001],g[500001],n,m,l,r[500001];
int lim,t,jc[10000001],ny[10000001],so[10000001];
int po[500001],pv[500001],ans,s;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}
inline int C(int x,int y){return mul(jc[y],mul(ny[y-x],ny[x]));}
inline int ksm(int x,int y){
    int num=1;
    while (y){
        if (y&1) num=mul(num,x);
        x=mul(x,x); y>>=1;
    }
    return num;
}
inline void NTT(int *a,int inv){
    for (int i=1; i<lim; i++)
        if (i<r[i]) swap(a[i],a[r[i]]);
    for (int i=1; i<lim; i<<=1){
        int wn=po[i]; if (inv<0) wn=pv[i];
        for (int j=0; j<lim; j+=(i<<1)){
            int w=1;
            for (int k=0; k<i; k++,w=mul(w,wn)){
                int x=a[j+k],y=mul(a[i+j+k],w);
                a[j+k]=add(x,y); a[i+j+k]=dec(x,y);
            }
        }
    }
    if (inv>0) return; inv=ksm(lim,mod-2);
    for (int i=0; i<lim; i++) a[i]=mul(a[i],inv);
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for (int i=0; i<=m; i++) scanf("%d",&w[i]);
    jc[0]=jc[1]=ny[0]=ny[1]=so[1]=1; t=max(n,m);
    for (int i=2; i<=t; i++){
        jc[i]=mul(jc[i-1],i);
        so[i]=mul(dec(mod,mod/i),so[mod%i]);
        ny[i]=mul(ny[i-1],so[i]);
    }
    t=min(m,n/s);
    for (int i=0,d=1; i<=t; i++,d=mod-d){
        f[t-i]=mul(C(i,m),C(i*s,n));
        f[t-i]=mul(f[t-i],mul(jc[i*s],ksm(ny[s],i)));
        f[t-i]=mul(f[t-i],ksm(m-i,n-i*s));
        f[t-i]=mul(f[t-i],jc[i]);
        g[i]=mul(d,ny[i]);
    }
    // for (int i=0; i<=t; i++) printf("%d ",g[i]); puts("");
    lim=1;
    while (lim<=t+t) lim<<=1,l++;
    for (int i=1; i<=lim; i++){
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
        po[i]=ksm(rt,(mod-1)/(i<<1));
        pv[i]=ksm(po[i],mod-2);
    }
    NTT(f,1); NTT(g,1);
    for (int i=0; i<lim; i++) f[i]=mul(f[i],g[i]);
    NTT(f,-1);
    for (int i=0; i<=t; i++) ans=add(ans,mul(mul(w[i],f[t-i]),ny[i]));
    printf("%d\n",ans);
    return 0;
}