[HAOI2018]染色（容斥+NTT）

颜色数不超过lim=min(m,n/S)，然后计算恰好出现S次的颜色有至少i种的方案数为f[i]，被钦定的i种恰好S个，其余(m-i)种一共(n-iS)个，然后f[i]=C(i,m)(m-i)^n-iSn!/((S!)ⁱ(n-iS)!)，然后一减就发现ans[i]=Σ(-1)^j-iC(i,j)f[j]，其中i<=j<=lim，然后拆项+移项，可以得到ans[i]*i!=Σ(-1)^j-if[j]*j!/(j-i)!，然后直接NTT一波就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=262200,mod=1004535809;
int n,m,s,nn,ans,fac[10000010],inv[10000010],val[N],A[N],B[N],R[N];
int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)ret=1ll*ret*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return ret;
}
int C(int a,int b){return a<b?0:1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;}
void NTT(int*a,int f)
{
    for(int i=0;i<nn;i++)if(i<R[i])swap(a[i],a[R[i]]);
    for(int i=1;i<nn;i<<=1)
    {
        int wn=qpow(3,mod/(i<<1));
        if(f==-1)wn=qpow(wn,mod-2);
        for(int j=0;j<nn;j+=i<<1)
        for(int k=0,w=1;k<i;k++,w=1ll*w*wn%mod)
        {
            int x=a[j+k],y=1ll*w*a[i+j+k]%mod;
            a[j+k]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
        }
    }
    if(f==1)return;
    int invn=qpow(nn,mod-2);
    for(int i=0;i<nn;i++)a[i]=1ll*a[i]*invn%mod;
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<=m;i++)scanf("%d",&val[i]);
    int mx=max(n,m);
    fac[0]=1;for(int i=1;i<=mx;i++)fac[i]=1ll*fac[i-1]*i%mod;
    inv[mx]=qpow(fac[mx],mod-2);
    for(int i=mx;i;i--)inv[i-1]=1ll*inv[i]*i%mod;
    int L=0,lim=min(m,n/s);nn=1;
    while(nn<(lim+1)*2)nn<<=1,L++;
    for(int i=0;i<=lim;i++)
    A[i]=1ll*fac[i]*C(m,i)%mod*fac[n]%mod*qpow(m-i,n-i*s)%mod*qpow(1ll*qpow(fac[s],i)*fac[n-i*s]%mod,mod-2)%mod;
    for(int i=0;i<=lim;i++)
    {
        B[i]=qpow(fac[lim-i],mod-2);
        if((lim-i)&1)B[i]=mod-B[i];
    }
    for(int i=0;i<nn;i++)R[i]=(R[i>>1]>>1)|(i&1)<<L-1;
    NTT(A,1),NTT(B,1);
    for(int i=0;i<nn;i++)A[i]=1ll*A[i]*B[i]%mod;
    NTT(A,-1);
    for(int i=0;i<=lim;i++)ans=(ans+1ll*val[i]*A[lim+i]%mod*qpow(fac[i],mod-2))%mod;
    printf("%d",ans);
}