好像网上没人....和我推出....同一个式子啊.....
题意
$ n$个格子中每个格子可以涂$ m$种颜色中的一种
若有$ k$种颜色恰好涂了$ s$格则产生$ w_k$的价值
求所有涂色方案的价值和
$ solution$
按常规套路先容斥
设 $f_x$表示恰好有$ x$种颜色涂了恰好$s$格的方案数，
$ g_x$表示至少有$ x$种颜色涂了恰好$ s$格的方案数
有
$ ans=\sum\limits_{i=0}^mw_if_i$
$ f_x=\sum\limits_{i=x}^m (-1)^{i-x}\binom{i}{x}g_i$
$ g_x=\binom{m}{x}\binom{n}{sx}\frac{(sx)!}{(s!)^x}(m-x)^{n-sx}$
其中$ g_x$的意义即为选出$x$种颜色，选出$ sx$个格子放置这些颜色，
并将其他$ m-x$种颜色在其他格子乱放的方案数
因此有
$ans=\sum\limits_{i=0}^mw_i\sum\limits_{j=i}^m(-1)^{j-i}\binom{j}{i}g_j$
将组合数展开成阶乘得
$ans=\sum\limits_{i=0}^mw_i\sum\limits_{j=i}^m(-1)^{j-i}\frac{j!}{i!(j-i)!}g_j$
设
$F_x=\frac{(-1)^x}{x}$，$G_x=g_xx!$
则有
$ans=\sum\limits_{i=0}^m\frac{w_i}{i!}\sum\limits_{j=i}^mF_{j-i}G_j$
将$ F$或$ G$反转之后后式是一个卷积形式
而$F$和$G$都可以快速计算
$NTT$优化即可
时间复杂度$ O(m \ log \ m + n)$
$ my \ code$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define p 1004535809
#define rt register int
#define ll long long
using namespace std;
inline char __getchar(){
static const int IN_LEN = ;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, , IN_LEN, stdin), (s == t ? - : *s++) : *s++);
}
#define getchar() __getchar()
inline ll read(){
ll x = ; char zf = ; char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (isdigit(ch)) x = x * + ch - '', ch = getchar(); return x * zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt;
int ksm(int x,int y){
int ans=;
for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*x*ans%p;
return ans;
}
int njc[],jc[];
void init(int N){
njc[]=njc[]=jc[]=jc[]=;
for(rt i=;i<=N;i++)jc[i]=1ll*i*jc[i-]%p;
njc[N]=ksm(jc[N],p-);
for(rt i=N-;i>=;i--)njc[i]=1ll*njc[i+]*(i+)%p;
}
inline int C(int x,int y){return 1ll*jc[x]*njc[y]%p*njc[x-y]%p;}
int w[],g[],f[],R[];
void NTT(int n,int *A,int fla){
for(rt i=;i<n;i++)if(i>R[i])swap(A[i],A[R[i]]);
for(rt i=;i<n;i<<=){
int w=ksm(,(p-)//i);
for(rt j=;j<n;j+=(i<<)){
int K=;
for(rt k=;k<i;k++,K=1ll*K*w%p){
int x=A[j+k],y=1ll*K*A[i+j+k]%p;
A[j+k]=(x+y)%p;A[i+j+k]=(x-y)%p;
}
}
}
if(fla==-){
reverse(A+,A+n);int invn=ksm(n,p-);
for(rt i=;i<n;i++)A[i]=1ll*invn*A[i]%p;
}
}
int main(){
n=read();m=read();int s=read();
ll ans=;init(max(n,m));
for(rt i=;i<=m;i++)w[i]=read();
for(rt j=,invv=;j<=m&&s*j<=n;j++,invv=1ll*invv*njc[s]%p)
g[j]=1ll*C(m,j)*C(n,s*j)%p*jc[s*j]%p*invv%p*ksm(m-j,n-s*j)%p*jc[j]%p; for(rt i=,tag=;i<=m;i++,tag*=-)f[i]=tag*njc[i];
reverse(f,f+m+);
int lim=;while(lim<=m+m)lim<<=;
for(rt i=;i<lim;i++)R[i]=(R[i>>]>>)|(i&)*(lim>>);
NTT(lim,f,);NTT(lim,g,);
for(rt i=;i<lim;i++)f[i]=1ll*f[i]*g[i]%p;
NTT(lim,f,-);
for(rt i=;i<=m;i++)(ans+=1ll*f[i+m]*w[i]%p*njc[i]%p)%=p;
cout<<(ans+p)%p;
return ;
}