Siyuan

「Luogu 4841」城市规划
「Luogu 4841」城市规划
扫描右侧二维码阅读全文
06
2019/07

「Luogu 4841」城市规划

题目链接:Luogu 4841

阿狸的国家有 $n$ 个城市,现在国家需要在某些城市对之间建立一些贸易路线,使得整个国家的任意两个城市都直接或间接的连通。

为了省钱,每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案,如果存在一个城市对,在两个方案中是否建立路线不一样,那么这两个方案就是不同的,否则就是相同的。现在你需要求出一共有多少不同的方案。

换句话说,你需要求出 $n$ 个点的简单(无重边无自环)无向连通图数目。由于这个数字可能非常大,你只需要输出方案数对 $1004535809 = 479 \times 2 ^ {21} + 1$ 取模的值即可。

数据范围:$1 \le n \le 1.3 \times 10 ^ 5$。


Solution

有标号无向连通图计数。

设 $f_i$ 表示 $i$ 个点的无向连通图数量,$g_i$ 表示 $i$ 个点的无向图数量。那么我们考虑 $f_i, g_i$ 的指数型生成函数:

$$ F(x) = \sum_{i = 0} ^ {\infty} \frac{f_i x^i}{i!} $$

我们枚举连通块数量 $k$ 得到:

$$ G(x) = \sum_{k = 0} ^ {\infty} \frac{F ^ k (x)}{k!} $$

即:

$$ G = e ^ F \\ F = \ln G $$

显然有:

$$ g_i = \frac{2 ^ {\binom{i}{2}}}{i!} $$

直接上多项式板子!

时间复杂度:$\mathcal O(n \log n)$。


Code

#include <cstdio>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
#include <unordered_map>

typedef std::vector<int> Vec;

const int MOD = 1004535809, G = 3;

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
void sub(int &x, int y) {
    (x -= y) < 0 && (x += MOD);
}
int add(int x) {
    return x >= MOD ? x - MOD : x;
}
int sub(int x) {
    return x < 0 ? x + MOD : x;
}
void mod(int &x) {
    x >= MOD && (x -= MOD), x < 0 && (x += MOD);
}
int mul(int x, int y) {
    return 1LL * x * y % MOD;
}
int pow(int x, int k) {
    int ans = 1;
    for (; k; k >>= 1, x = 1LL * x * x % MOD) {
        if (k & 1) ans = 1LL * ans * x % MOD;
    }
    return ans;
}
int inv(int x) {
    return pow(x, MOD - 2);
}
int BSGS(int a, int b, int p) {
    std::unordered_map<int, int> mp;
    int m = ceil(sqrt(p));
    for (int i = 0; i <= m; b = 1LL * b * a % p, i++) mp[b] = i;
    a = pow(a, m);
    for (int i = 0, j = 1; i < m; j = 1LL * j * a % p, i++) {
        if (mp.count(j) && i * m >= mp[j]) {
            return i * m - mp[j];
        }
    }
    return -1;
}
int degree(int a, int k, int p) {
    int x = BSGS(G, a, p);
    assert(x >= 0 && x % k == 0);
    int r = pow(G, x / k);
    return std::min(r, p - r);
}

namespace FFT {
    int extend(int x);
    void NTT(Vec &A, bool opt);
    void DFT(Vec &A);
    void IDFT(Vec &A);

    int extend(int x) {
        int n = 1;
        for (; n < x; n <<= 1);
        return n;
    }
    void NTT(Vec &A, bool opt) {
        int n = A.size(), k = 0;
        for (; (1 << k) < n; k++);
        Vec rev(n);
        for (int i = 0; i < n; i++) {
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << (k - 1);
            if (i < rev[i]) std::swap(A[i], A[rev[i]]);
        }
        for (int l = 2; l <= n; l <<= 1) {
            int m = l >> 1, w = pow(G, (MOD - 1) / l);
            if (opt) w = inv(w);
            for (int j = 0; j < n; j += l) {
                int wk = 1;
                for (int i = 0; i < m; i++, wk = 1LL * wk * w % MOD) {
                    int p = A[i + j], q = 1LL * wk * A[i + j + m] % MOD;
                    A[i + j] = (p + q) % MOD;
                    A[i + j + m] = (p - q + MOD) % MOD;
                }
            }
        }
    }
    void DFT(Vec &A) {
        NTT(A, false);
    }
    void IDFT(Vec &A) {
        NTT(A, true);
        int t = inv(A.size());
        for (auto &x : A) x = 1LL * x * t % MOD;
    }
}
using namespace FFT;

namespace Poly {
    Vec operator + (Vec A, Vec B);
    Vec operator + (Vec A, int v);
    Vec operator + (int v, Vec A);
    Vec operator - (Vec A, Vec B);
    Vec operator - (Vec A, int v);
    Vec operator - (int v, Vec A);
    Vec operator - (Vec A);
    Vec operator * (Vec A, Vec B);
    Vec operator * (Vec A, int v);
    Vec operator * (int v, Vec A);
    Vec operator / (Vec A, Vec B);
    Vec operator / (Vec A, int v);
    Vec operator % (Vec A, Vec B);
    Vec operator ~ (Vec A);
    Vec operator ^ (Vec A, int k);
    Vec operator << (Vec A, int x);
    Vec operator >> (Vec A, int x);
    Vec fix(Vec A, int n);
    Vec der(Vec A, bool mod);
    Vec inte(Vec A, bool mod);
    Vec sqrt(Vec A);
    Vec root(Vec A, int k);
    Vec ln(Vec A);
    Vec exp(Vec A);
    Vec sin(Vec A);
    Vec cos(Vec A);
    Vec tan(Vec A);
    Vec asin(Vec A);
    Vec acos(Vec A);
    Vec atan(Vec A);
    void print(Vec A);

    Vec operator + (Vec A, Vec B) {
        int n = std::max(A.size(), B.size());
        A.resize(n), B.resize(n);
        for (int i = 0; i < n; i++) add(A[i], B[i]);
        return A;
    }
    Vec operator + (Vec A, int v) {
        add(A[0], v);
        return A;
    }
    Vec operator + (int v, Vec A) {
        add(A[0], v);
        return A;
    }
    Vec operator - (Vec A, Vec B) {
        int n = std::max(A.size(), B.size());
        A.resize(n), B.resize(n);
        for (int i = 0; i < n; i++) sub(A[i], B[i]);
        return A;
    }
    Vec operator - (Vec A, int v) {
        sub(A[0], v);
        return A;
    }
    Vec operator - (int v, Vec A) {
        A = -A, add(A[0], v);
        return A;
    }
    Vec operator - (Vec A) {
        for (auto &x : A) x = sub(-x);
        return A;
    }
    Vec operator * (Vec A, Vec B) {
        int n = A.size() + B.size() - 1, N = extend(n);
        A.resize(N), DFT(A);
        B.resize(N), DFT(B);
        for (int i = 0; i < N; i++) A[i] = 1LL * A[i] * B[i] % MOD;
        IDFT(A), A.resize(n);
        return A;
    }
    Vec operator * (Vec A, int v) {
        for (auto &x : A) x = 1LL * x * v % MOD;
        return A;
    }
    Vec operator * (int v, Vec A) {
        for (auto &x : A) x = 1LL * x * v % MOD;
        return A;
    }
    Vec operator / (Vec A, Vec B) {
        int n = A.size() - B.size() + 1;
        if (n <= 0) return Vec(1, 0);
        std::reverse(A.begin(), A.end());
        std::reverse(B.begin(), B.end());
        A.resize(n), B.resize(n);
        A = fix(A * ~B, n);
        std::reverse(A.begin(), A.end());
        return A;
    }
    Vec operator / (Vec A, int v) {
        return A * inv(v);
    }
    Vec operator % (Vec A, Vec B) {
        int n = B.size() - 1;
        return fix(A - A / B * B, n);
    }
    Vec operator ~ (Vec A) {
        int n = A.size(), N = extend(n);
        A.resize(N);
        Vec I(N, 0);
        I[0] = inv(A[0]);
        for (int l = 2; l <= N; l <<= 1) {
            Vec P(l), Q(l);
            std::copy(A.begin(), A.begin() + l, P.begin());
            std::copy(I.begin(), I.begin() + l, Q.begin());
            int L = l << 1;
            P.resize(L), DFT(P);
            Q.resize(L), DFT(Q);
            for (int i = 0; i < L; i++) {
                P[i] = 1LL * Q[i] * (2 - 1LL * P[i] * Q[i] % MOD + MOD) % MOD;
            }
            IDFT(P), P.resize(l);
            std::copy(P.begin(), P.begin() + l, I.begin());
        }
        I.resize(n);
        return I;
    }
    Vec operator ^ (Vec A, int k) {
        int n = A.size(), x = 0;
        for (; x < n && A[x] == 0; x++);
        if (1LL * x * k >= n) return Vec(n, 0);
        A = A >> x;
        int v = A[0];
        return (exp(ln(A) * k) * pow(v, k)) << (x * k);
    }
    Vec operator << (Vec A, int x) {
        int n = A.size();
        Vec B(n, 0);
        for (int i = 0; i < n - x; i++) B[i + x] = A[i];
        return B;
    }
    Vec operator >> (Vec A, int x) {
        int n = A.size();
        Vec B(n, 0);
        for (int i = 0; i < n - x; i++) B[i] = A[i + x];
        return B;
    }
    Vec fix(Vec A, int n) {
        A.resize(n);
        return A;
    }
    Vec der(Vec A, bool mod = true) {
        int n = A.size();
        if (n == 1) return Vec(1, 0);
        Vec D(n - 1, 0);
        for (int i = 1; i < n; i++) D[i - 1] = 1LL * i * A[i] % MOD;
        if (mod) D.resize(n);
        return D;
    }
    Vec inte(Vec A, bool mod = true) {
        int n = A.size();
        Vec I(n + 1, 0);
        for (int i = 1; i <= n; i++) I[i] = 1LL * inv(i) * A[i - 1] % MOD;
        if (mod) I.resize(n);
        return I;
    }
    Vec sqrt(Vec A) {
        int n = A.size(), N = extend(n);
        A.resize(N);
        Vec R(N, 0);
        R[0] = degree(A[0], 2, MOD);
        int i2 = inv(2);
        for (int l = 2; l <= N; l <<= 1) {
            Vec P(l), Q(l);
            std::copy(A.begin(), A.begin() + l, P.begin());
            std::copy(R.begin(), R.begin() + l, Q.begin());
            Vec I = ~Q;
            int L = l << 1;
            P.resize(L), DFT(P);
            Q.resize(L), DFT(Q);
            I.resize(L), DFT(I);
            for (int i = 0; i < L; i++) {
                Q[i] = 1LL * Q[i] * Q[i] % MOD;
                P[i] = 1LL * (P[i] + Q[i]) * i2 % MOD * I[i] % MOD;
            }
            IDFT(P), P.resize(l);
            std::copy(P.begin(), P.begin() + l, R.begin());
        }
        R.resize(n);
        return R;
    }
    Vec root(Vec A, int k) {
        return k == 1 ? A : k == 2 ? sqrt(A) : exp(ln(A) / k);
    }
    Vec ln(Vec A) {
        assert(A[0] == 1);
        int n = A.size();
        return inte(fix(der(A) * ~A, n));
    }
    Vec exp(Vec A) {
        assert(A[0] == 0);
        int n = A.size(), N = extend(n);
        A.resize(N);
        Vec E(N, 0);
        E[0] = 1;
        for (int l = 2; l <= N; l <<= 1) {
            Vec P = (-ln(fix(E, l)) + fix(A, l) + 1) * fix(E, l);
            std::copy(P.begin(), P.begin() + l, E.begin());
        }
        E.resize(n);
        return E;
    }
    Vec sin(Vec A) {
        assert(A[0] == 0);
        int i = degree(MOD - 1, 2, MOD);
        Vec E = exp(A * i);
        return (E - ~E) / (2LL * i % MOD);
    }
    Vec cos(Vec A) {
        assert(A[0] == 0);
        int i = degree(MOD - 1, 2, MOD);
        Vec E = exp(A * i);
        return (E + ~E) / 2;
    }
    Vec tan(Vec A) {
        assert(A[0] == 0);
        int n = A.size();
        return fix(sin(A) * ~cos(A), n);
    }
    Vec asin(Vec A) {
        assert(A[0] == 0);
        int n = A.size();
        return inte(fix(der(A) * ~sqrt(1 - fix(A * A, n)), n));
    }
    Vec acos(Vec A) {
        assert(A[0] == 0);
        return -asin(A);
    }
    Vec atan(Vec A) {
        assert(A[0] == 0);
        int n = A.size();
        return inte(fix(der(A) * ~(1 + fix(A * A , n)), n));
    }
    void print(Vec A) {
        int n = A.size();
        for (int i = 0; i < n; i++) printf("%d%c", A[i], " \n"[i == n - 1]);
    }
}
using namespace Poly;

int main() {
    int n;
    scanf("%d", &n);
    Vec A(n + 1);
    A[0] = 1;
    int fac = 1, c = 0;
    for (int i = 1; i <= n; i++) {
        fac = 1LL * fac * i % MOD;
        A[i] = 1LL * pow(2, c) * inv(fac) % MOD;
        c = (c + i) % (MOD - 1);
    }
    printf("%d\n", 1LL * ln(A)[n] * fac % MOD);
    return 0;
}
最后修改:2019 年 07 月 06 日 08 : 53 PM

发表评论