bzoj5093

NTT+组合数学

$把每个点分别按度数考虑，由于有标号，可以得出$

$ans=n*2^{(n-1)*(n-2)}*\sum_{i=1}^{n-1}{C(n-1,i)*i^{k}}$

$本质上是求\sum_{i=1}^{n}{C(n,i)*i^{k}}$

$组合数永远是一个比较好化简的东西，问题在于i^{k}$

$通常有两种方式可以化简，一种利用第二类斯特林数，另一种是利用伯努利数，这里利用第二类斯特林数的组合意义$

$考虑i^{k}的组合意义，相当于把k个不同的物品放进i个不同的箱子$

$S(n,k)表示把n个不同元素拆成k个集合的方案数$

$注意这里要枚举集合数，因为箱子允许空，集合不允许空，所以转化成加法原理$

$考虑转化，枚举多少个箱子有东西，也就是拆成几个集合$

$n^{k}=\sum_{i=1}^{n}{S(k,i)*C(n,i)*i!}$

$得出\sum_{i=1}^{n}{C(n,i)*i^{k}}=\sum_{i=1}^{n}{C(n,i)\sum_{j=1}^{i}{S(k,j)*C(i,j)*j!}}$

$然而并无卵用，这个东西还是不能快速求$

$改变求和顺序\sum_{j=1}^{n}{S(k,j)*j!\sum_{i=j}^{n}{C(n,i)*C(i,j)}}$

$考虑里面组合数的意义，C(n,i)*C(i,j),表示先从n个里选了i个，再从i个里选j个，相当于先选j个，剩下的随便选不选$

$那么就是C(n,j)*2^{n-j}，里面的sigma消掉了$

$所以变成\sum_{j=1}^{n}{S(k,j)*j!*C(n,j)*2^{n-j}}$

$问题就变成了如何快速求第二类斯特林数$

$由于给定了k，所以我们可以通过NTT快速预处理出斯特林数$

$考虑容斥原理，S(k,j)表示将k个不同的数划分成j个集合，那么j个集合都非空$

$用容斥原理弱化这个式子，\frac{1}{j!}\sum_{i=0}^{j}{(-1)^{i}*C(j,i)*(j-i)^{k}}$

$先保证至少，那么i个集合是空的，剩下的随便放，那么放k个数的方案就是(j-i)^{k}$

$但是这里的集合是无序的，所以我们还得除一个j!$

$化简一下得出S(k,j)=\sum_{i=0}^{j}{\frac{(-1)^{i}}{i!}*\frac{(j-i)^{k}}{(j-i)!}}$

$这很卷积，那么直接NTT预处理第二类斯特林数，然后O(n)算出答案即可$

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e5 + , P = ;

int n, m, k, len;

ll ans;

ll a[N << ], b[N << ], fac[N], inv[N], facinv[N], fac_n[N];

ll power(ll x, ll t) {

    ll ret = ;

    for(; t; t >>= , x = x * x % P) {

        if(t & ) {

            ret = ret * x % P;

        }

    }

    return ret;

}

void ntt(ll *a, int f) {

    for(int i = ; i < n; ++i) {

        int t = ;

        for(int j = ; j < len; ++j) {

            if(i >> j & ) {

                t |=  << (len - j - );

            }

        }

        if(i < t) {

            swap(a[i], a[t]);

        }

    }

    for(int l = ; l <= n; l <<= ) {

        int m = l >> ;

        ll w = power(, f ==  ? (P - ) / l : (P - ) - (P - ) / l);

        for(int i = ; i < n; i += l) {

            ll t = ;

            for(int k = ; k < m; ++k, t = t * w % P) {

                ll x = a[i + k], y = t * a[i + m + k] % P;

                a[i + k] = (x + y) % P;

                a[i + k + m] = ((x - y) % P + P) % P;

            }

        }

    }

    if(f == -) {

        ll inv = power(n, P - );

        for(int i = ; i < n; ++i) {

            a[i] = a[i] * inv % P;

        }

    }

}

int main() {

    scanf("%d%d", &m, &k);

    --m;

    fac[] = ;

    inv[] = ;

    facinv[] = ;

    fac_n[] = ;

    for(int i = ; i <= k; ++i) {

        fac[i] = fac[i - ] * i % P;

        fac_n[i] = fac_n[i - ] * (m - i + ) % P;

        if(i != ) {

            inv[i] = (P - P / i) * inv[P % i] % P;

        }

        facinv[i] = facinv[i - ] * inv[i] % P;

    }

    n = ;

    len = ;

    while(n <= k * ) {

        n <<= ;

        ++len;

    }

    for(int i = ; i <= k; ++i) {

        a[i] = facinv[i] * ((i & ) ? - : );

        a[i] = ((a[i] % P) + P) % P;

        b[i] = power(i, k) * facinv[i] % P;

    }

    ntt(a, );

    ntt(b, );

    for(int i = ; i < n; ++i) {

        a[i] = a[i] * b[i] % P;

    }

    ntt(a, -);

    for(int i = ; i <= k && i <= m; ++i) {

        ans = (ans + a[i] * fac[i] % P * facinv[i] % P * fac_n[i] % P * power(, m - i) % P) % P;

    }

    ans = ans * (m + ) % P * power(, (ll)m * (m - ) / ) % P;

    printf("%lld\n", ans);

    return ;

}

巴特西

bzoj5093

最新文章

热门文章