bzoj3456 城市规划

题目描述

刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了.

刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出一共有多少不同的方案.

好了, 这就是困扰阿狸的问题. 换句话说, 你需要求出n个点的简单(无重边无自环)无向连通图数目.

由于这个数字可能非常大, 你只需要输出方案数mod 1004535809(479 * 2 ^ 21 + 1)即可.

输入格式

仅一行一个整数n(<=130000)

输出格式

仅一行一个整数, 为方案数 mod 1004535809.

样例输入

3

样例输出

4

说明

对于 100%的数据, n <= 130000


分析

设$f(i)$表示点数为$i$的无向连通图个数,则:

$$f(i)=2^{C(i,2)}-\sum_{j=1}^{i-1}f(j)\cdot C(i-1,j-1)\cdot 2^{C(n-j, 2)}$$

就是总方案数减去不连通的方案数,枚举与点$1$连通的点即可转移。

现在要考虑的是如何快速求出$f(n)$,所以尽量把式子往卷积的方向靠。

把$C(i-1,j-1)$拆开:

$$f(i)=2^{C(i,2)}-\sum_{j=1}^{i-1}f(j)\cdot \frac{(i-1)!}{(j-1)!\cdot (i-j)!}\cdot 2^{C(i-j, 2)}$$

观察一下式子,两边同除$(i-1)!$,把相似的部分写在一起:

$$\frac{f(i)}{(i-1)!}=2^{C(i,2)}-\sum_{j=1}^{i-1}\frac{f(j)}{(j-1)!}\cdot \frac{2^{C(i-j,2)}}{(i-j)!}$$

有点像卷积的形式,移项得:

$$\sum_{j=1}^{i}\frac{f(j)}{(j-1)!}\cdot \frac{2^{C(i-j,2)}}{(i-j)!}=2^{C(i,2)}$$

设:

$$A=\sum_{i=1}^{n}\frac{f(j)}{(j-1)!}x^i$$

$$B=\sum_{i=0}^{n}\frac{2^{C(n-i,2)}}{(n-i)!}x^i$$

$$C=\sum_{i=1}^{n}2^{C(i,2)}x^i$$

则$A\times B=C$,那么$A=B\times C^{-1} \pmod {x^{n+1}}$,多项式求逆即可。

代码

#include <bits/stdc++.h>
typedef long long ll;

const int N = 6e5;
const int P = 1004535809;
const int G = 3;

int qPow(int x, ll k) {
    int rtn = 1;
    for (; k; k >>= 1, x = (ll)x * x % P)
        if (k & 1) rtn = (ll)rtn * x % P;
    return rtn;
}

int inv(int x) {
    return qPow(x, P-2);
}

namespace NTT {
    int n, rev[N];
    int ta[N], tb[N];

    void ntt(int f[], int sgn) {
        for (int i = 0; i < n; i++)
            if (rev[i] > i) std::swap(f[i], f[rev[i]]);
        for (int i = 1; i < n; i <<= 1) {
            int gn = qPow(G, (P-1)/(i*2));
            if (sgn == -1) gn = inv(gn);
            for (int j = 0; j < n; j += i << 1) {
                int g = 1;
                for (int k = 0; k < i; k++, g = (ll)g * gn % P) {
                    int x = f[j+k], y = (ll)g * f[j+i+k] % P;
                    f[j+k] = (x + y) % P;
                    f[j+i+k] = (x - y) % P;
                }
            }
        }
        if (sgn == -1) {
            int invn = inv(n);
            for (int i = 0; i < n; i++)
                f[i] = (ll)f[i] * invn % P;
        }
        for (int i = 0; i < n; i++)
            f[i] = (f[i] + P) % P;
    }

    void init(int m) {
        int len = 0;
        for (n = 1; n < m; n <<= 1, len++);
        for (int i = 1; i < n; i++)
            rev[i] = rev[i>>1] >> 1 | (i&1) << len-1;
    }

    void mul(int la, int lb, const int a[], const int b[], int res[]) {
        memset(ta, 0, sizeof ta);
        memset(tb, 0, sizeof tb);
        memcpy(ta, a, sizeof(int) * la);
        memcpy(tb, b, sizeof(int) * lb);
        init(la+lb-1);
        ntt(ta, 1);
        ntt(tb, 1);
        for (int i = 0; i < n; i++)
            ta[i] = (ll)ta[i] * tb[i] % P;
        ntt(ta, -1);
        memcpy(res, ta, sizeof(int) * (la+lb-1));
    }
}

void getInv(int n, const int a[], int b[]) {
    if (n == 1) {
        b[0] = inv(a[0]);
        return;
    }
    getInv(n+1>>1, a, b);
    NTT::init(n<<1);
    int _n = NTT::n;
    static int c[N];
    memcpy(c, a, sizeof(int)*n);
    memset(c+n, 0, sizeof(int)*(_n-n));
    memset(b+n, 0, sizeof(int)*(_n-n));
    NTT::ntt(b, 1);
    NTT::ntt(c, 1);
    for (int i = 0; i < _n; i++)
        b[i] = (2LL - (ll)b[i] * c[i] % P) * b[i] % P;
    NTT::ntt(b, -1);
    memset(b+n, 0, sizeof(int)*(_n-n));
    for (int i = 0; i < n; i++)
        b[i] = (b[i] + P) % P;
}

int n;
int fac[N], ifac[N];
int A[N], B[N], C[N], iB[N];

int T(int i) {
    return qPow(2, (ll)i * (i-1) / 2);
}

int main() {
    scanf("%d", &n);

    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (ll)fac[i-1] * i % P;
    ifac[n] = inv(fac[n]);
    for (int i = n-1; i >= 0; i--)
        ifac[i] = (ll)ifac[i+1] * (i+1) % P;

    for (int i = 0; i <= n; i++)
        B[i] = (ll)T(i) * ifac[i] % P;
    for (int i = 1; i <= n; i++)
        C[i] = (ll)T(i) * ifac[i-1] % P;
    getInv(n+1, B, iB);
    NTT::mul(n+1, n+1, C, iB, A);
    int ans = (ll)A[n] * fac[n-1] % P;
    ans = (ans + P) % P;
    printf("%d\n", ans);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论