Luogu

LOJ

分析

显然一块画布上出现次数为 $S$ 的颜色不超过 $L=\min\left\{m,\left\lfloor\frac{n}{S}\right\rfloor\right\}$ 种。

考虑容斥。设 $f_i$ 为出现次数为 $S$ 的颜色有至少 $i$ 种的方案数，不难得到
$$
f_i={m\choose i}\frac{n!}{(S!)^i(n-iS)!}(m-i)^{n-iS}
$$
设 $g_i$ 为出现次数为 $S$ 的颜色有恰好 $i$ 种的方案数，则
$$
f_i=\sum_{j=i}^L{j\choose i}g_j
$$
二项式反演得到
$$
g_i=\sum_{j=i}^L(-1)^{j-i}{j\choose i}f_j
$$
拆开得到
$$
g_i\times i!=\sum_{j=i}^mj!f_j\times\frac{(-1)^{j-i}}{(j-i)!}
$$
可以发现是一个差卷积的形式，于是直接 NTT 即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=262144+10,M=10000000+10;
const int mod=1004535809;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,m,S,w[N];
int fac[M],ifac[M],f[N],g[N],F[N],G[N];

int C(int n,int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int r[N];
void NTT(int* A,int n,int op) {
    for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?3:334845270,(mod-1)/(i<<1));
        for (int j=0;j<n;j+=i<<1)
            for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (op==-1) { int inv=qpow(n,mod-2);
        for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}

int main() {
    n=read(),m=read(),S=read(); int L=min(m,n/S);
    for (int i=0;i<=m;++i) w[i]=read();
    fac[0]=1;
    for (int i=1;i<=max({n,m,S});++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[max({n,m,S})]=qpow(fac[max({n,m,S})],mod-2);
    for (int i=max({n,m,S});i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
    for (int i=0;i<=L;++i)
        f[i]=1ll*C(m,i)*fac[n]%mod*qpow(ifac[S],i)%mod
            *ifac[n-i*S]%mod*qpow(m-i,n-i*S)%mod;
    for (int i=0;i<=L;++i) F[i]=1ll*fac[i]*f[i]%mod;
    for (int i=0;i<=L;++i) G[L-i]=i&1?mod-ifac[i]:ifac[i];
    int lim=1,l=-1;
    for (;lim<=L+L;lim<<=1,++l);
    for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l);
    NTT(F,lim,1),NTT(G,lim,1);
    for (int i=0;i<lim;++i) F[i]=1ll*F[i]*G[i]%mod;
    NTT(F,lim,-1);
    for (int i=0;i<=L;++i) g[i]=1ll*F[L+i]*ifac[i]%mod;
    int ans=0;
    for (int i=0;i<=L;++i) ans=(ans+1ll*g[i]*w[i])%mod;
    printf("%d\n",ans);
    return 0;
}