【HAOI2018】染色

by AmanoKumiko

Description

为了报答小\(C\)的苹果, 小\(G\)打算送给热爱美术的小\(C\)一块画布, 这块画布可以抽象为一个长度为\(N\)的序列, 每个位置都可以被染成\(M\)种颜色中的某一种.

然而小\(C\)只关心序列的\(N\)个位置中出现次数恰好为\(S\)的颜色种数, 如果恰好出现了\(S\)次的颜色有\(K\)种, 则小\(C\)会产生\(W_k\)的愉悦度.

小\(C\)希望知道对于所有可能的染色方案, 他能获得的愉悦度的和对\(1004535809\)取模的结果是多少.

Input

从标准输入读入数据.第一行三个整数\(N,M,S\)

接下来一行\(M+1\)个整数，第\(i\)个表示\(W_{i-1}\)

Output

输出到标准输出中. 输出一个整数表示答案．

Sample Input

8 8 3
3999 8477 9694 8454 3308 8961 3018 2255 4910

Sample Output

524070430

Data Constraint

\(1\le n\le 10^7,1\le m\le 10^5,0\le S\le 150\)

Solution

直接考虑对于每个\(w\)计算贡献求和：

\[n!\sum_{i=0}^mw_i\frac{1}{(S!)^i}C_m^i[x^{n-Si}](\sum_{j=0}[j≠S]\frac{x^j}{j!})^{m-i} \]

发现后面那部分不好算，考虑容斥：

\[\sum_{i=0}^mw_iC_m^i\sum_{j=0}^{m-i}C_{m-i}^j(-1)^j\frac{[(i+j)S]!}{(S!)^{i+j}}(m-i-j)^{n-(i+j)S}C_n^{(i+j)S} \]

令\(k=i+j\)

则有：

\[\sum_{k=0}^m\frac{m!(ks)!(m-k)^{n-ks}C_n^{ks}}{(m-k)!(s!)^k}\sum_{i+j=k}\frac{w_i(-1)^j}{i!j!} \]

大力卷积即可

Code

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 10000010
#define mo 1004535809

int rev[N],n,m,s;
LL fac[N],ifac[N],ans,w[N];
LL mi(LL x,LL y){
	LL res=1;
	for(;y;y>>=1){if(y&1)(res*=x)%=mo;(x*=x)%=mo;}
	return res;
}
void BRP(int x){
	int bit=log2(x);
	F(i,0,x-1)rev[i]=(rev[i>>1]>>1)|((i&1)?1<<bit-1:0);
}
struct poly{
	vector<LL>val;
	void build(){val.clear();}
	void rsz(int x){
		while(val.size()>x)val.pop_back();
		while(val.size()<x)val.push_back(0);
	}
	void NTT(int x){
		F(i,0,val.size()-1)if(rev[i]<i)swap(val[rev[i]],val[i]);
		for(int mid=1;mid<val.size();mid<<=1){
			LL gn=mi(3,(mo-1)/(mid*2));
			if(x==-1)gn=mi(gn,mo-2);
			for(int i=0;i<val.size();i+=mid*2){
				LL g=1;
				F(j,0,mid-1){
					LL le=val[i+j],ri=val[i+j+mid]*g%mo;
					val[i+j]=(le+ri)%mo;val[i+j+mid]=(le-ri+mo)%mo;
					(g*=gn)%=mo;
				}
			}
		}
		if(x==-1){
			LL inv=mi(val.size(),mo-2);
			F(i,0,val.size()-1)(val[i]*=inv)%=mo;
		}
	}
	void DFT(){NTT(1);}
	void IDFT(){NTT(-1);}
}f,g;

poly operator*=(poly&x,poly y){
	int l=1,s=x.val.size()+y.val.size();
	while(l<x.val.size()+y.val.size()+1)l<<=1;
	x.rsz(l);
	y.rsz(l);
	BRP(l);
	x.DFT();y.DFT();
	F(i,0,l-1)(x.val[i]*=y.val[i])%=mo;
	x.IDFT();x.rsz(s);
	return x;
}

LL C(int x,int y){return fac[x]*ifac[y]%mo*ifac[x-y]%mo;}

int main(){
	scanf("%d%d%d",&n,&m,&s);
	F(i,0,m)scanf("%lld",&w[i]);
	ifac[0]=fac[0]=1;F(i,1,N-10)fac[i]=fac[i-1]*i%mo;
	ifac[N-10]=mi(fac[N-10],mo-2);Fd(i,N-11,1)ifac[i]=ifac[i+1]*(i+1)%mo;
	F(i,0,m)f.val.push_back(ifac[i]*w[i]%mo),g.val.push_back(i&1?mo-ifac[i]:ifac[i]);
	f*=g;
	LL Pow=1;
	F(i,0,m){
		if(i*s>n)break;
		(ans+=fac[m]*ifac[m-i]%mo*fac[i*s]%mo*Pow%mo*C(n,i*s)%mo*mi(m-i,n-i*s)%mo*f.val[i]%mo)%=mo;
		(Pow*=ifac[s])%=mo;
	}
	printf("%lld",ans);
	return 0;
}