bzoj 5306[HAOI 2018]染色

http://www.elijahqi.win/archives/3800 テーマ背景HAOI 2018 Round 2第二題
テーマはCさんのりんごに報いるために、Gさんは美術を愛するCさんにキャンバスをあげようとしたが、このキャンバスは長さを抽象化することができる.
N
Nのシーケンスは、位置ごとに染められます
M
M種の色のいずれかである.
しかし、Cちゃんはシーケンスの
N
N箇所での出現回数は
S
Sの色種数は、ちょうど現れたら
S
S次の色は
K
K種だとCちゃんが
W_k
Wkの楽しさ
Cさんはすべての可能な染色案に対して、彼が得ることができる喜びの和を知りたいと思っています.
1004535809
1004535809型取りの結果はいくらですか.
入出力フォーマット入力フォーマット:
標準入力からデータを読み込む.1行目の3つの整数
N, M, S
N,M,S .
次の行
M + 1
M+1個の整数、第
i個数表示
Wi−1 W i − 1
出力フォーマット:
標準出力に出力.整数で答えを表す.
入出力サンプル入力サンプル#1:コピー
8 8 8 3 3999 8477 9694 8454 3308 8961 3018 2255 4910出力サンプル#1:コピー
524070430入力サンプル#2:コピー
に会うhttps://www.luogu.org/paste/rxrv9utg 出力サンプル#2:コピー
231524284は特殊な性質を説明する.
∀1≤i≤m,Wi=0 ∀ 1 ≤ i ≤ m , W i = 0
100%100%のデータに対して、
0≤Wi<1004535809 0 ≤ W i < 1004535809
lim=min(m,n/s)つまり最大何個のS長の色を置くと仮定して現在k個のs長の色があると仮定してシナリオ数Ckmを求めてみる×(Csm×Csm−s...)×(m−k)n−ks C m k × ( C m s × C m − s s . . . ) × (m−k)n−k sは、このように繰り返し計算があることを発見することができるので、g[m][n]がk色の中の色の任意の組み合わせを含まず、s長が二度と現れないことを示すシナリオ数を2つのセグメントに分けて計算してもよい.(m−i)!×i!n!(s!)i(n−s)!∑j=0m−i(−1)j(m−i)!(m−i−j)!j!×(n−is)!(s!)j(n−js−is)!×(m−i−j)n−js−is ∑ i = 0 l i m m ! ( m − i ) ! × i ! n ! ( s ! ) i ( n − s ) ! ∑ j = 0 m − i ( − 1 ) j ( m − i ) ! ( m − i − j ) ! j ! × ( n − i s ) ! ( s ! ) j ( n − j s − i s ) ! × (m−i−j)n−j−s−i sはiとlimの交換が何の影響もないことを考慮しているので,iをlim−iと見なし,またjをj−iΣi=0 limmに置き換える!(m−i)!i!n!(s!)i(n−s)!∑j=ilim(−1)j−i(m−i)!(m−j)!(j−i)!×(n−is)!(s!)j−i(n−js−is)!(m−j)n−is ∑ i = 0 l i m m ! ( m − i ) ! i ! n ! ( s ! ) i ( n − s ) ! ∑ j = i l i m ( − 1 ) j − i ( m − i ) ! ( m − j ) ! ( j − i ) ! × ( n − i s ) ! ( s ! ) j − i ( n − j s − i s ) ! (m−j)n−i sは構造ボリューム形式mを考慮する!n!∑j=1lim(m−j)n−js(m−j)!(s!)j(n−js)!∑i=0jwii!(−1)j−i(j−i)! m ! n ! ∑ j = 1 l i m ( m − j ) n − j s ( m − j ) ! ( s ! ) j ( n − j s ) ! ∑ i = 0 j w i i ! ( − 1 ) j − i ( j − i ) !

#include
#define ll long long
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();
    return x*f;
}
const int g=3;
const int N=1e5+10;
const int mod=1004535809;
inline int ksm(ll b,int t){static ll tmp;
    for (tmp=1;t;b=b*b%mod,t>>=1) if (t&1) tmp=tmp*b%mod;return tmp;
}
inline int inc(int x,int v){return x+v>=mod?x+v-mod:x+v;}
inline int dec(int x,int v){return x-v<0?x-v+mod:x-v;}
int n,m,s,S,jc[N*100],inv[N*100],nn,a[N<<2],b[N<<2],R[N<<2],ans,w[N];
inline void ntt(int *x,int f){
    for (int i=0;iif (ix[i],x[R[i]]);
    for (int i=1;i1){
        ll wn=ksm(g,f==1?(mod-1)/(i<<1):mod-1-(mod-1)/(i<<1));
        for (int j=0;j1){
            ll w=1,t1,t2;
            for (int k=0;k*wn%mod){
                t1=x[j+k],t2=x[j+k+i]*w%mod;
                x[j+k]=inc(t1,t2);x[j+k+i]=dec(t1,t2);
            }
        }
    }
    if (f==-1){
        int invn=ksm(n,mod-2);
        for (int i=0;ix[i]=(ll)x[i]*invn%mod;
    }
}
int main(){
    freopen("bzoj5306.in","r",stdin);
    n=read();m=read();s=read();S=1;jc[0]=1;nn=n;
    for (int i=0;i<=m;++i) w[i]=read();int lim=min(m,n/s);
    for (int i=1;i<=s;++i) S=(ll)S*i%mod;S=ksm(S,mod-2);int nm=max(n,m);
    for (int i=1;i<=nm;++i) jc[i]=(ll)jc[i-1]*i%mod;inv[nm]=ksm(jc[nm],mod-2);
    for (int i=nm-1;~i;--i) inv[i]=(ll)inv[i+1]*(i+1)%mod;int l=0;
    for (n=1;n<=lim<<1;n<<=1,++l);for (int i=0;i>1]>>1)|((i&1)<1);
    for (int i=0;i<=lim;++i) a[i]=(ll)inv[i]*w[i]%mod,b[i]=inv[i]*((i&1)?-1:1),b[i]=inc(b[i],mod);
    //n=4;a[0]=1;a[1]=2;b[0]=1;b[1]=2;b[2]=1;
    ntt(a,1);ntt(b,1);
    for (int i=0;i*b[i]%mod;ntt(a,-1);
    for (int i=0;i<=lim;++i) 
    ans=inc(ans,(ll)ksm(m-i,nn-s*i)*inv[m-i]%mod*ksm(S,i)%mod*inv[nn-i*s]%mod*a[i]%mod);
    ans=(ll)ans*jc[nn]%mod*jc[m]%mod;printf("%d
",ans);
    return 0;
}