BZOJ3456 城市规划

题意

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

题解

对于一类组合对象,定义 $A$ 为初始元素集合的 $EGF$
然后定义函数 $SET(A)=\sum_{i\geq 0} \cfrac{A^i}{i!}$ 表示有这些元素有序拼接组成的组合对象的生成函数
对于 $e^x$ 做皮亚诺余项泰勒展开
$$ e^x=\sum_{n\geq 0}\cfrac{x^n}{n!} $$

于是 $SET(A)$ 等价于 $e^A$
两个带标号的简单无向图拼接显然可以用 $EGF$
设 $G(x)$ 为简单无向连通图的 $EGF$ ,$F(x)$ 为简单无向图的 $EGF$
由于简单无向图可以看成若干个简单无向连通图有序拼接而成所以有
$$ F(x)=e^{G(x)} $$

$$ G(x)=\ln F(x) $$
显然有
$$ F(x)=\sum_{n\geq 0} 2^{C_n^2}\cfrac{x^n}{n!} \ \ \ \ (1)$$
所以
$$ G(x)=\ln F(x)=\int \cfrac{F'(x)}{F(x)} \ \ \ \ (2)$$
联立 $(1),(2)$ 可以解出 $G(x)$
然后问题就解决了
只不过我跑的好慢啊

代码

#define MAX_N 2000007
#define MOD 1004535809
#define G 3LL

int N;
ll a[MAX_N], b[MAX_N], c[MAX_N], tmp[MAX_N];
int r[MAX_N];

void trans (int deg, ll *a, ll *b) {
    if (deg == 1) {
        b[0] = quick_pow(a[0], MOD - 2);
        return;
    }
    trans((deg + 1) >> 1, a, b);
    int M = 1, len = 0;
    while (M < (deg << 1)) M <<= 1, ++len;
    for (int i = 0; i < M; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1);
    for (int i = 0; i < deg; ++i)
        tmp[i] = a[i];
    for (int i = deg; i < M; ++i)
        tmp[i] = 0;
    NTT(tmp, M, 1), NTT(b, M, 1);
    for (int i = 0; i < M; ++i)
        b[i] = (2LL - tmp[i] * b[i] % MOD + MOD) % MOD * b[i] % MOD;
    NTT(b, M, -1);
    for (int i = deg; i < M; ++i)
        b[i] = 0;
}

inline void transln (ll *a, ll *b, ll *c, int N) {
    trans(N, a, b); //b = 1/a
    int M = 1, len = 0;
    while (M < (N << 1)) M <<= 1, ++len;
    for (int i = 0; i < M; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << len - 1);
    for (int i = 0; i < M; ++i)
        c[i] = a[i + 1] * (ll)(i + 1) % MOD;
    NTT(c, M, 1), NTT(b, M, 1);
    for (int i = 0; i < M; ++i)
        c[i] = b[i] * c[i] % MOD;
    NTT(c, M, -1), NTT(b, M, -1); //b->1/a, c->a'/a
    for (int i = N - 1; i > 0; --i)
        c[i] = c[i - 1] * quick_pow((ll)i, MOD - 2) % MOD;
    c[0] = 0;
}

inline void input () {
    read(N);
    N++;
}

inline ll C (ll x, ll y) {
    if (x < y) return 0;
    if (x == y) return 1;
    return (x - 1) * x / 2 % (MOD - 1);
}

inline void init () {
    ll bs = 1;
    for (int i = 0; i < N; ++i) {
        a[i] = quick_pow(2LL, C((ll)i, 2LL)) * quick_pow(bs, MOD - 2) % MOD;
        (bs *= (ll)(i + 1)) %= MOD;
    }
}

inline void solve () {
    transln(a, b, c, N);
    ll bs = 1LL;
    for (int i = 1; i < N; ++i)
        (bs *= (ll)i) %= MOD;
    printf("%lld\n", c[N - 1] % MOD * bs % MOD);
}

int main () {
    input();
    init();
    solve();
    return 0;
}

引用资料

lc 讲课资料

sys_con

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

发表评论

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