Description
为了报答小 (C) 的苹果, 小 (G) 打算送给热爱美术的小 (C) 一块画布, 这块画布可 以抽象为一个长度为 (N) 的序列, 每个位置都可以被染成 (M) 种颜色中的某一种.
然而小 (C) 只关心序列的 (N) 个位置中出现次数恰好为 (S) 的颜色种数, 如果恰 好出现了 (S) 次的颜色有 (K) 种, 则小 (C) 会产生 (W_k) 的愉悦度.
小 (C) 希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对 (1004535809) 取模的结果是多少.
Solution
[ans=sumlimits_{i=0} ^{min(m,lfloor frac{n}S
floor)} w_i imes method(i)
]
做一些卷积题目就会猜一下这个 (method(i)) 可能是要卷积出来的东西
那么推一下这个 (method(i))
[method(i)=inom M iinom N {iS} (m-i)^{n-iS} imes frac{(iS)!}{(S!)^i}
]
然后就错了，因为最后的乱放可能再次出现有 (S) 个颜色
那么容斥这个过程，设最终出现了 (S) 次的颜色种类数是 (j) 那么得到如下：
[method(i)=inom M iinom N{iS}frac{(iS)!}{(S!)^i} sumlimits _ {j=i} ^M (-1)^{j-i} inom {M-i}{j-i} inom {n-iS}{(j-i)S} frac{((j-i)S)!}{(S!)^{j-i}}(m-j)^{N-jS}
]
这式子貌似不短
那么化简完了 (NTT) 即可得到答案
把所有的组合数打开得到
[method(i)=frac{N!M!}{i!} sumlimits_{j=i}^M frac{(-1)^{j-i}}{(j-i)!}frac{(M-j)^{n-jS}}{(M-j)!(N-jS)(S!)^j}
]
减法卷积可以翻转完了直接做，但是如果有梦想也可以推成加法卷积
[sum_{j=0}^Nfrac{N!M!(m-j)^{N-jS}}{(S!)^j(N-jS)!(M-j)!} sum_{i=0}^j frac{w_i}{i!} imesfrac{(-1)^{j-i}}{(j-i)!}
]
(Theta(nlog n+n)) 即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
namespace yspm{
inline int read(){
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int mod=1004535809,N=1e7+10,G=3;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int del(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return x*y-x*y/mod*mod;}
inline int ksm(int x,int y){int res=1; for(;y;y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x); return res;}
int w[N],ans,n,m,S;
const int M=5e5+10;
int f[M],g[M],r[M];
inline void NTT(int *f,int lim,int fl){
for(reg int i=0;i<lim;++i) if(i<r[i]) swap(f[i],f[r[i]]);
for(reg int p=2;p<=lim;p<<=1){
int len=p>>1,tmp=ksm(G,(mod-1)/p); if(fl==-1) tmp=ksm(tmp,mod-2);
for(reg int k=0;k<lim;k+=p){
int buf=1; for(reg int l=k;l<k+len;++l){
int tt=mul(buf,f[l+len]); f[l+len]=del(f[l],tt); f[l]=add(f[l],tt);
buf=mul(buf,tmp);
}
}
} if(fl==-1) for(reg int i=0;i<lim;++i) f[i]=mul(f[i],ksm(lim,mod-2)); return ;
}
int fac[N],inv[N],i2[N];
signed main(){
n=read(); m=read(); S=read(); for(reg int i=0;i<=m;++i) w[i]=read();
fac[0]=fac[1]=i2[0]=i2[1]=inv[1]=inv[0]=1; for(reg int i=2;i<N;++i) fac[i]=mul(fac[i-1],i),i2[i]=mul(i2[i-1],inv[i]=mod-mul(mod/i,inv[mod%i]));
for(reg int i=0;i<=m;++i) f[i]=mul(w[i],i2[i]),g[i]=mul((i&1)?mod-1:1,i2[i]);
int lim=1; while(lim<=(m<<1)) lim<<=1; for(reg int i=0;i<lim;++i) r[i]=r[i>>1]>>1|((i&1)?(lim>>1):0);
NTT(f,lim,1); NTT(g,lim,1); for(reg int i=0;i<lim;++i) f[i]=mul(f[i],g[i]); NTT(f,lim,-1);
for(reg int j=0;j<=n;++j){
if(n-j*S<0||m-j<=0) break;
int r1=ksm(m-j,n-j*S),r2=mul(ksm(fac[S],j),mul(fac[m-j],fac[n-j*S])); r2=ksm(r2,mod-2);
ans=add(ans,mul(mul(r1,r2),f[j]));
} printf("%lld
",mul(ans,mul(fac[m],fac[n])));
return 0;
}
}
signed main(){return yspm::main();}