bzoj3456

分治+ntt

设dp[i]表示i个点的图联通的方案数

那么考虑dp，利用容斥，总-不符合，枚举j=1->i-1,然后考虑不符合，那么考虑和1联通的连通块，剩下的不和1连通，那么dp[i]=2^t(i)-∑j=1->i-1 dp[j]*C(i-1,j-1)*2^t(i-j)

就是t(i)表示i个点的图的边的个数，那么相当于在j个点的连通图又添加了i-j个点，计算从i-1选出j-1个方案数，这是组合数，然后剩下的不能喝这j个点连，那么自己内部随便连，就是这个式子

但是这是n^2的，我们化简式子变成卷积，dp[j]*C(i-1,j-1)*2^t(i-j)

dp[j]*(i-1)!/(j-1)!/(i-j)!*2^t(i-j)

(dp[j]/(j-1)!)*2^t(i-j)/(i-j)

这是卷积，但是由于dp[i]和dp[j]有关，那么用cdq优化。

这是第二次写，还是搞不太清楚下标问题，其实就是构造多项式的时候每个式子个往前移了多少，那么最后统计的时候也往后移动多少

完全不卡常啊

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = , P = ;

int n, m, k;

ll h[N], a[N], b[N], inv[N], facinv[N], fac[N], dp[N], t[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 < k; ++j) if(i >> j & ) t |=  << (k - j - );

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

    }

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

    {

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

        int m = 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 = a[i + k + m] * t % 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;

    }

}

void cdq(int l, int r)

{

    if(l == r) return;

    int mid = (l + r) >> ;

    cdq(l, mid);

    n = ;

    k = ;

    while(n <= r - l + ) n <<= , ++k;

    for(int i = ; i < n; ++i) a[i] = b[i] = ;

    for(int i = l; i <= mid; ++i) a[i - l] = dp[i] * facinv[i - ] % P;

    for(int i = ; i <= r - l; ++i) b[i] = h[i] * 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 = mid + ; i <= r; ++i) dp[i] = ((dp[i] - a[i - l] * fac[i - ] % P) % P + P) % P;

    cdq(mid + , r);

}

int main()

{

    scanf("%d", &m);

    fac[] = facinv[] = ;

    inv[] = inv[] = ;

    for(int i = ; i <= m; ++i)

    {

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

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

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

        t[i] = (ll)i * (i - ) >> ;

        dp[i] = h[i] = power(, t[i]);

    }

    cdq(, m);

    printf("%lld\n", dp[m]);

    return ;

}

巴特西

bzoj3456

最新文章

热门文章