记录编号	578118	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2018]染色	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	1.955 s
提交时间	2023-02-01 20:22:10	内存使用	111.36 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define fi first
#define se second
#define pb push_back
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
const int N=(1<<17)+5;
const int M=10000000+5;
const ll mod=1004535809;
ll fst(ll x,ll y){
    ll ans=1;
    while(y){
        if (y&1)ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
const ll _G=3;
const ll invG=fst(_G,mod-2);
int tr[N<<1],tf=0;
ll fac[M],inv[M];
void init(int n){
    fac[0]=1;
    for (int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    inv[n]=fst(fac[n],mod-2);
    for (int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
void tpre(int n){
    if (n==tf)return ;
    for (int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
    tf=n;
}
void NTT(ll *g,int n,bool opt){
    static ll f[N<<1],w[N<<1];
    tpre(n);w[0]=1;
    for (int i=0;i<n;i++)f[i]=g[tr[i]];
    for (int p=2;p<=n;p<<=1){
        int len=p>>1;
        ll tG=fst(opt?_G:invG,(mod-1)/p);
        for (int i=1;i<len;i++)w[i]=w[i-1]*tG%mod;
        for (int i=0;i<n;i+=p){
            for (int j=i;j<i+len;j++){
                ll now=f[j+len]*w[j-i]%mod;
                f[j+len]=(f[j]-now+mod)%mod;
                f[j]=(f[j]+now)%mod;
            }
        }
    }
    if (opt)for (int i=0;i<n;i++)g[i]=f[i];
    else{
        ll invn=fst(n,mod-2);
        for (int i=0;i<n;i++)g[i]=f[i]*invn%mod;
    }
}
void px(ll *f,ll *g,int n){
    for (int i=0;i<n;i++)f[i]=f[i]*g[i]%mod;
}
void times(ll *f,ll *g,int len,int lim){
    static ll sav[N<<1];
    int n=1;for (;n<=len;n<<=1);
    clr(sav,n);cpy(sav,g,n);
    NTT(f,n,1);NTT(sav,n,1);
    px(f,sav,n);NTT(f,n,0);
    if (lim)clr(f+lim,n-lim);
    clr(sav,n);
}
int n,m,s;
ll a[N<<1],b[N<<1],w[N<<1];
ll C(int x,int y){
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
ll g(int i){
    if (n-i*s<0)return 0;
    return C(m,i)*fac[n]%mod*inv[n-i*s]%mod*fst(inv[s],i)%mod*fst(m-i,n-i*s)%mod;
}
int main(){
	freopen ("2018color.in","r",stdin);
	freopen ("2018color.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	for (int i=0;i<=m;i++)scanf("%lld",&w[i]);
	init(max(n,m));
	for (int i=0;i<=m;i++){
	    a[i]=fac[i]*g(i);
	    b[i]=(i&1)?mod-inv[i]:inv[i];
    }
    reverse(a,a+m+1);
    times(a,b,m<<1,m+1);
    reverse(a,a+m+1);
    ll ans=0;
    for (int i=0;i<=m;i++)ans=(ans+a[i]*inv[i]%mod*w[i]%mod)%mod;
    printf("%lld\n",ans);
    return 0;
}