传送门

二项式反演套路题啊。。。

看到“恰好”想“至少”。设$f(i)$为恰好$i$种颜色出现次数为$S$，$g(i)$为至少$i$种颜色出现次数为$S$。

$g(i)$很好算。$C_m^i$钦定$i$种颜色，$\dfrac{A_n^{iS}}{(S!)^i}$钦定位置和顺序，剩下$n-iS$个位置和$m-i$种颜色随便填，为$(m-i)^{n-iS}$。

即$g(i)=\dfrac{C_m^iA_n^{iS}(m-i)^{n-iS}}{(S!)^i}$

对于一种恰好$i$种颜色出现次数为$S$的方案，它会在$g(j)$中被计算$C_j^i$次。

即$g(i)=\sum\limits_{j=i}^mC_j^if(j)$

二项式反演，$f(i)=\sum\limits_{j=i}^m(-1)^{j-i}C_j^ig(j)$

把$g(j)$带进去，组合数展开，化简一下，得到：

$f(i)=\dfrac{n!m!}{i!}\sum\limits_{j=i}^m\dfrac{(-1)^{j-i}(m-j)^{n-jS}}{(j-i)!(n-jS)!(m-j)!(S!)^j}$

这个式子的$j$从$i$开始，不太好看。统一把$j$换成$m-j$，再分个类：

$f(i)=\dfrac{n!m!}{i!}\sum\limits_{j=0}^{m-i}\dfrac{(-1)^{m-i-j}}{(m-i-j)!}\times \dfrac{j^{n-(m-j)S}}{[n-(m-j)S]!j!(S!)^{m-j}}$

这显然是个卷积的形式。令多项式$F_i=\dfrac{(-1)^i}{i!},G_i=\dfrac{i^{n-(m-i)S}}{[n-(m-i)S]!i!(S!)^{m-i}}$，$NTT$卷起来。

答案就是$n!m!\sum\limits_{i=0}^m\dfrac{W_i\times (F*G)_{m-i}}{i!}$

复杂度$O(n+m\log m)$。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 500005
#define inf 0x3f3f3f3f

const int mod = 1004535809;
const int g = 3;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
inline int quickpow(int x,int y=mod-2){
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod,y>>=1;
    }
    return ans;
}
const int ig = quickpow(g);
int fac[10000005]={1},inv[10000005],rev[maxn],F[maxn],G[maxn];
inline int mix(int x,int y){return x+y>=mod?x+y-mod:x+y;}
void NTT(int *f,int n,bool type){
    static int invn = quickpow(n);
    for(register int i=0;i<n;++i)if(i<rev[i])swap(f[i],f[rev[i]]);
    for(register int p=2;p<=n;p<<=1){
        int len=p>>1,o=quickpow(type?ig:g,(mod-1)/p);
        for(register int i=0;i<n;i+=p){
            int gen=1,cop;
            for(register int j=i;j<i+len;++j){
                cop=1ll*f[j+len]*gen%mod;
                f[j+len]=mix(f[j],mod-cop),f[j]=mix(f[j],cop),gen=1ll*gen*o%mod;
            }
        }
    }
    if(type)for(register int i=0;i<n;++i)f[i]=1ll*f[i]*invn%mod;
}
void init(int n){
    for(register int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=quickpow(fac[n]);
    for(register int i=n-1;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int main(){
    int n=read(),m=read(),s=read(),lim=1,ans=0;
    init(max(n,max(m,s)));
    while(lim<=m<<1)lim<<=1;
    for(register int i=1;i<lim;++i)rev[i]=(rev[i>>1]>>1)|(i&1?lim>>1:0);
    for(register int i=0;i<=m;++i){
        F[i]=i&1?mod-inv[i]:inv[i];
        if(n>=(m-i)*s)G[i]=1ll*quickpow(i,n-(m-i)*s)*inv[n-(m-i)*s]%mod*inv[i]%mod*quickpow(inv[s],m-i)%mod;
    }
    NTT(F,lim,0),NTT(G,lim,0);
    for(register int i=0;i<lim;++i)F[i]=1ll*F[i]*G[i]%mod;
    NTT(F,lim,1);
    for(register int i=0;i<=m;++i){
        int w=read();
        ans=mix(ans,1ll*w*F[m-i]%mod*inv[i]%mod);
    }
    printf("%d\n",1ll*ans*fac[m]%mod*fac[n]%mod);
}