icontofig | 发布于 2019-10-12 15:06:43 | 阅读量 121 | NTT 数学 组合数
发布于 2019-10-12 15:06:43 | NTT 数学 组合数
#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxm = 1e5+5;
const int maxn = 1e7+5;
typedef long long ll;
const ll mod = 1004535809;
ll fac[maxn],inv[maxn],w[maxm],f[maxm<<2],finv[maxn];
ll b[maxm<<2];
int rev[maxm<<2];
void init(int x){
    fac[0] = fac[1] = inv[0] = inv[1] = finv[0] = finv[1] = 1ll;
    for(int i = 2;i <= x;++i){
        fac[i] = fac[i-1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        finv[i] = finv[i-1] * inv[i] % mod;
    }
    return;
}
ll quick_pow(ll a,ll b,ll mod){
    ll ret = 1;
    while(b){
        if(b & 1)
            ret = (ret * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ret;
}
ll g;
int len,lg;
void NTT_init(int k){
    len = 1;lg = 0;
    for(len = 1;len < k;len <<= 1,lg++);
    for(int i = 0;i < len;++i)
        rev[i] = (rev[i>>1]>>1) | ((i & 1) << (lg - 1));
}
void NTT(ll *a,int len,int f){
    for(int i = 0;i < len;++i){
        if(i < rev[i])
            swap(a[i],a[rev[i]]);
    }
    for(int i = 2;i <= len;i <<= 1){
        int now = i >> 1;
        ll wn = quick_pow(g,(mod-1)/i,mod);
        if(f == -1)wn = quick_pow(wn,mod-2,mod) % mod;
        for(int j = 0;j < len;j += i){
            ll wk = 1,x,y;
            for(int k = j;k < j + now;k++,wk = wk * wn % mod){
                x = a[k];
                y = a[k + now] * wk % mod;
                a[k] = (x + y) % mod;
                a[k + now] = (x - y + mod) % mod;
            } 
        }
    }
    if(f == -1){
        ll invn = quick_pow(len,mod-2,mod);
        for(int i = 0;i < len;++i)
            a[i] = a[i] * invn % mod;
    }
    return;
}
ll C(int x,int y){
    return fac[x] * finv[y] % mod * finv[x-y] % mod;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> s;
    ll lim = min(n/s,m);
    init(max(n,m));
    g = 3;
    for(int i = 0;i <= m;++i)
        cin >> w[i];
    for(int i = 0;i <= lim;++i){
//        if(i * s > n)break;
        f[i] = C(m,i) * fac[n] % mod * finv[n-s*i] % mod * quick_pow(finv[s],i,mod)
            % mod * quick_pow(m-i,n-s*i,mod) % mod * fac[i] % mod;
    }
    for(int i = 0;i <= lim;++i)
        b[i] = ((lim-i) & 1) ? (mod - finv[lim-i]) : finv[lim-i];
    NTT_init(lim+lim+2);
    NTT(f,len,1);NTT(b,len,1);
    for(int i = 0;i < len;++i)
        f[i] = f[i] * b[i] % mod;
    NTT(f,len,-1);
    ll ans = 0;
    for(int i = 0;i <= lim;++i){
        ans += f[i+lim] * finv[i] % mod * w[i] % mod;
        ans %= mod;
    }
    cout << ans << "\n";
    return 0;
}

 


内容更新于: 2019-10-12 15:06:45
链接地址: http://blog.leanote.com/post/icontofig/9e451a2961f0

上一篇: HAOI2018 染色 NTT 组合数 生成函数

下一篇: 牛客国庆欢乐赛5 2017四川省赛 D.Dynamic Graph bitset加速 + topsort

121 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航