BZOJ3456 城市规划 – 2

题意

给出 $n$ ,请求出点数为 $n$ 的简单无向联通图个数

题解

之前这篇面讲了多项式对数的做法
这里讲个分治 NTT 的方法
设 $f_n$ 表示大小为 $n$ 的图的方案,那么枚举 1 所在的连通块大小,有转移:
$$
\begin{eqnarray}
f_i&=&2^{{i\choose 2}}-\sum_{j=1}^{i-1}{i-1\choose j-1}\cdot 2^{{i-j\choose 2}}\cdot f_j\\
&=&2^{{i\choose 2}}-(i-1)!\sum_{j=1}^{i-1}\frac{f_j}{(j-1)!}\cdot \frac{2^{{i-j\choose 2}}}{(i-j)!}
\end{eqnarray}
$$

然后发现后面是一个和 $f_j$ 有关的卷积,分治 NTT 一下就行了
复杂度 $O(n\log^2(n))$ ,但是比我之前写的 $O(n\log(n))$ 做法还快

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 150007
#define MOD 1004535809
#define G 3
#define rep(i, l, r) for(int i = l, ed = r; i <= ed; ++i)
#define lep(i, l, r) for(int i = l, ed = r; i < ed; ++i)
typedef long long ll;

template <typename _T>
inline bool read (_T& x) {
    x = 0;
    _T y = 1;
    char c = getchar();
    while ((c < '0' || '9' < c) && c != EOF) {
        if (c == '-') y = -1;
        c = getchar();
    }
    if (c == EOF) return false;
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
    x *= y;
    return true;
}

inline int add (int x, int y) {
    x += y;
    return x >= MOD ? x - MOD : x;
}

inline int mul (int x, int y) { return 1LL * x * y % MOD; }

inline int qpow (int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = mul(ans, x);
        y >>= 1;
        x = mul(x, x);
    }
    return ans;
}

int N;
int gx[MAX_N << 1], igx[MAX_N << 1], rev[MAX_N << 1];

inline int init (int N) {
    int M = 1, l = 0;
    while (M <= N) {
        gx[M] = qpow(G, (MOD - 1) / (M << 1));
        igx[M] = qpow(gx[M], MOD - 2);
        M <<= 1;
        ++l;
    }
    gx[M] = qpow(G, (MOD - 1) / (M << 1));
    igx[M] = qpow(gx[M], MOD - 2);
    lep (i, 0, M) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << l - 1);
    return M;
}

inline void NTT (int *A, int len, int tp) {
    lep (i, 0, len) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
    for (int l = 1; l < len; l <<= 1) {
        int gn = (tp == 1 ? gx[l] : igx[l]);
        for (int i = 0, L = l << 1; i < len; i += L) {
            for (int j = i, x, y, g = 1, ed = i + l; j < ed; ++j, g = mul(g, gn)) {
                x = A[j], y = mul(A[j + l], g);
                A[j] = add(x, y), A[j + l] = add(x, MOD - y);
            }
        }
    }
    if (tp == 1) return;
    int inv = qpow(len, MOD - 2);
    lep (i, 0, len)
        A[i] = mul(A[i], inv);
}

int fac[MAX_N << 1], ifac[MAX_N << 1], pw[MAX_N << 1];
int f[MAX_N << 1], g[MAX_N << 1], h[MAX_N << 1];

void solve (int l, int r) {
    if (l == r) {
        f[l] = add(pw[l], MOD - mul(fac[l - 1], f[l]));
        return;
    }
    int mid = l + r >> 1;
    solve(l, mid);
    int L = r - l + 1, M = init(L);
    g[0] = h[0] = 0;
    rep (i, 1, mid - l + 1) g[i] = mul(f[i + l - 1], ifac[i + l - 2]);
    lep (i, mid - l + 2, M) g[i] = 0;
    rep (i, 1, L) h[i] = mul(pw[i], ifac[i]);
    lep (i, L + 1, M) h[i] = 0;
    NTT(g, M, 1), NTT(h, M, 1);
    lep (i, 0, M) g[i] = mul(g[i], h[i]);
    NTT(g, M, -1);
    rep (i, mid + 1, r) f[i] = add(f[i], g[i - l + 1]);
    solve(mid + 1, r);
}

int main () {
    read(N);
    int M = init(N);
    ifac[0] = fac[0] = 1;
    rep (i, 1, M) fac[i] = mul(fac[i - 1], i);
    ifac[M] = qpow(fac[M], MOD - 2);
    for (int i = M - 1; i; --i)
        ifac[i] = mul(ifac[i + 1], i + 1);
    pw[0] = pw[1] = 1;
    rep (i, 2, M) pw[i] = qpow(2, 1LL * i * (i - 1) / 2LL % (MOD - 1));
    solve(1, N);
    printf("%d\n", f[N]);
    return 0;
} 

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注