【BZOJ3456】城市规划

题目

转送门

思路&算法

我们设点数为$n$的简单图的数量为$f_n$, 点数为$n$的简单连通图有$g_i$个

于是我们知道,从$n$个点中选$2$个点有$n \choose 2$种选法, 而对于两个点可以连边或不连, 于是$f_n = 2^{n \choose 2}$

同时, $f_n$还满足$f_n = \sum\limits_{i = 1}^{n}{n-1 \choose {i-1}}g_if_{n-i}$, 因为我们可以考虑钦定某一点为联通块中的一点, 然后从剩余的点中找$i-1$个点, 练成一个联通块, 剩下随便, 然后$i$取遍$1 \sim n$中的所有数后的和为$f_n$。

于是, 我们来愉快的推式子$$2^{n \choose 2} = \sum_{i = 1}^{n}{{n-1} \choose {i-1}}g_if_{n-i}$$

把$f_n = 2^{n \choose 2}$带入$$2^{n \choose 2} = \sum_{i = 1}^{n}{{n-1} \choose {i-1}}2^{{n-i\;} \choose {2}}g_i$$

$$2^{n \choose 2} = \sum_{i = 1}^{n}\frac{{(n-1)!}/{(i-1)!}}{(n-i)!}g_i2^{{n-i\;} \choose 2}$$

$$2^{n \choose 2} = \sum_{i = 1}^{n}\frac{{(n-1)!}}{(n-i)!(i-1)!}g_i2^{{n-i\;} \choose {2}}$$

$$2^{n \choose 2} = (n-1)!\sum_{i = 1}^{n}\frac{1}{(i-1)!(n-i)!}g_i2^{{n-i\;} \choose {2}}$$

$$\frac{2^{{n} \choose 2}}{(n-1)!} = \sum_{i=1}^{n}\frac{1}{(n-i)!(n-1)!}g_i2^{{n-i\;} \choose {2}}$$

$$\frac{2^{{n} \choose 2}}{(n-1)!} = \sum_{i=1}^{n} \left(\frac{1}{n-i}2^{{n-i\;} \choose {2}}\right)\left(\frac{1}{(i-1)!}g_i\right)$$

这是一个卷积

我们令$A(x) = \sum\limits_{i = 1}^{n}\frac{1}{(i-1)!}2^{i \choose 2}x^i$, $B(x) = \sum\limits_{i = 1}^{n}\frac{1}{(i-1)!}g_{i-1}x^i$, $C(x) = \sum\limits_{i = 0}^{n-1}\frac{1}{i!}2^{i \choose 2}x^i$

于是$C(x) = A(x)B(x)$

然后$B(x) = A(x)C^{-1}(x)$

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 520010;

const LL mod = 1004535809LL;

inline LL power(LL a, LL n, LL mod)
{   LL Ans = 1;
    a %= mod;
    while (n)
    {   if (n & 1) Ans = (Ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return Ans;
}

struct Mul
{   int rev[N];
    int Len, Bit;

    LL wn[N];

    void getReverse()
    {   for (int i = 0; i < Len; i++)
            rev[i] = (rev[i>>1] >> 1) | ((i&1) * (Len >> 1));
    }

    void NTT(LL * a, int opt)
    {   getReverse();
        for (int i = 0; i < Len; i++)
            if (i < rev[i]) swap(a[i], a[rev[i]]);
        int cnt = 0;
        for (int i = 2; i <= Len; i <<= 1)
        {   cnt++;
            for (int j = 0; j < Len; j += i)
            {   LL w = 1LL;
                for (int k = 0; k < (i>>1); k++)
                {   LL x = a[j + k];
                    LL y = (w * a[j + k + (i>>1)]) % mod;
                    a[j + k] = (x + y) % mod;
                    a[j + k + (i>>1)] = (x - y + mod) % mod;
                    w = (w * wn[cnt]) % mod;
                }
            }
        }
        if (opt == -1)
        {   reverse(a + 1, a + Len);
            LL num = power(Len, mod-2, mod);
            for (int i = 0; i < Len; i++)
                a[i] = (a[i] * num) % mod;
        }
    }

    void getLen(int l)
    {   Len = 1, Bit = 0;
        for (; Len <= l; Len <<= 1) Bit++;
    }

    void init()
    {   for (int i = 0; i < 22; i++)
            wn[i] = power(3, (mod-1) / (1LL << i), mod);
    }
} Calc;

LL tmp1[N], tmp2[N];

void cpy(LL * A, LL * B, int len1, int len2)
{   for (int i = 0; i < len1; i++) A[i] = B[i];
    for (int i = len1; i < len2; i++) A[i] = 0;
}

void getInv(LL * A, LL * B, int Len)
{   B[0] = power(A[0], mod-2, mod);
    for (register int i = 2; i <= Len; i <<= 1)
    {   int l = i << 1;
        cpy(tmp1, A, i, l);
        cpy(tmp2, B, i>>1, l);
        Calc.Len = l;
        Calc.NTT(tmp1, 1);
        Calc.NTT(tmp2, 1);
        for (register int j = 0; j < l; j++)
            tmp1[j] = ((2LL * tmp2[j]) % mod + mod - ((tmp2[j] * tmp2[j]) % mod * tmp1[j]) % mod) % mod;
        Calc.NTT(tmp1, -1);
        for (register int j = 0; j < i; j++)
            B[j] = tmp1[j];
    }
}

LL A[N], B[N], Ans[N];

LL fac[N];

int main()
{   int n;
    scanf("%d", &n);
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i-1] * (LL) i) % mod;
    Calc.getLen(n);
    int len = Calc.Len;
    Calc.init();
    A[0] = 1;
    for (int i = 1; i < n; i++)
        A[i] = (power(2LL, (LL) i * (LL) (i-1) / 2LL, mod) * power(fac[i], mod-2, mod)) % mod;
    B[0] = 0;
    for (int i = 1; i <= n; i++)
        B[i] = (power(2LL, (LL) i * (LL) (i-1) / 2LL, mod) * power(fac[i-1], mod-2, mod)) % mod;
    getInv(A, Ans, len);
    Calc.Len = len << 1;
    Calc.NTT(Ans, 1);
    Calc.NTT(B, 1);
    for (int i = 0; i < Calc.Len; i++)
        Ans[i] = (Ans[i] * B[i]) % mod;
    Calc.NTT(Ans, -1);
    printf("%lld\n", (Ans[n] * fac[n-1]) % mod);
    return 0;
}

发表于 2018-07-25 19:43:25 in 多项式