题解：n个节点的有标号仙人掌计数

一、问题定义

仙人掌图：无重边、无自环的有标号连通无向图，且每条边至多属于一个简单回路。题目要求计算 $n$ 个节点的仙人掌图数量，答案对 $998244353$ 取模。

二、核心思路

仙人掌计数是经典的组合图计数问题，需通过递推公式结合预处理实现高效查询。

1. 关键定义：

   • $f(n)$：$n$ 个节点的有标号连通仙人掌数量。
   • $g(n)$：$n$ 个节点的有标号无向简单图总数，即 $g(n) = 2^{\binom{n}{2}}$（每个边可选/不选）。
   • 组合数 $C(n,k)$：从 $n$ 个元素中选 $k$ 个的方案数，需预处理阶乘、逆元快速计算。

2. 递推公式 仙人掌的递推基于“容斥原理”和“连通图分解”，核心公式为： [ f(n) = \frac{1}{n+1} \left( n \cdot g(n-1) - \sum_{k=1}^{n-2} \binom{n-2}{k-1} \cdot k \cdot f(k) \cdot g(n-k) \right) \mod 998244353 ] 其中：

• 边界条件：$f(1)=1$，$f(2)=1$（2个节点的唯一连通图是边，属于仙人掌）。
• $g(n)$ 可通过递推计算：$g(n) = g(n-1) \cdot 2^{n-1} \mod 998244353$（因 $\binom{n}{2} = \binom{n-1}{2} + n-1$）。

3. 预处理步骤 为支持多组查询，需预处理以下数组（预处理范围至 $n_{\text{max}}=131072$）：

• 阶乘/逆元/阶乘逆元：用于快速计算组合数 $C(n,k)$。
• 幂次数组：预处理 $2^m \mod 998244353$，用于计算 $g(n)$。
• $g(n)$数组：递推计算 $n$ 个节点的无向简单图总数。
• $f(n)$数组：通过递推公式计算每个 $n$ 对应的仙人掌数量。

三、代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 998244353;
const int MAXN = 131072 + 10;

long long fact[MAXN], inv_fact[MAXN], pow2[MAXN];
long long g[MAXN], f[MAXN];

// 快速幂
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘、逆元、阶乘逆元
void init_fact() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[MAXN-1] = qpow(fact[MAXN-1], MOD-2);
    for (int i = MAXN-2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

// 预处理2的幂次
void init_pow2() {
    pow2[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        pow2[i] = pow2[i-1] * 2 % MOD;
    }
}

// 计算组合数C(n, k)
long long comb(int n, int k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

// 预处理g数组：g[n] = 2^(n*(n-1)/2) mod MOD
void init_g() {
    g[1] = 1;
    for (int n = 2; n < MAXN; n++) {
        // g[n] = g[n-1] * 2^(n-1) mod MOD
        g[n] = g[n-1] * pow2[n-1] % MOD;
    }
}

// 预处理f数组：n个节点的有标号仙人掌数量
void init_f() {
    f[1] = 1;
    f[2] = 1;
    for (int n = 3; n < MAXN; n++) {
        long long sum = 0;
        for (int k = 1; k <= n-2; k++) {
            // 计算C(n-2, k-1) * k * f[k] * g[n-k]
            long long c = comb(n-2, k-1);
            long long term = c * k % MOD;
            term = term * f[k] % MOD;
            term = term * g[n - k] % MOD;
            sum = (sum + term) % MOD;
        }
        // 计算分子：n * g[n-1] - sum
        long long numerator = (1LL * n * g[n-1] % MOD - sum + MOD) % MOD;
        // 计算分母逆元：inv(n+1)
        long long inv_denominator = qpow(n + 1, MOD - 2);
        f[n] = numerator * inv_denominator % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 预处理所有数组
    init_fact();
    init_pow2();
    init_g();
    init_f();

    int Q;
    cin >> Q;
    while (Q--) {
        int n;
        cin >> n;
        cout << f[n] << '\n';
    }

    return 0;
}

四、代码说明

1. 预处理模块：

   • init_fact()：预处理阶乘和逆元，用于快速计算组合数。
   • init_pow2()：预处理 $2$ 的幂次，用于递推计算 $g(n)$。
   • init_g()：递推计算 $g(n) = 2^{\binom{n}{2}}$，利用 $\binom{n}{2} = \binom{n-1}{2} + n-1$ 优化。
   • init_f()：通过核心递推式计算每个 $n$ 的仙人掌数量，注意取模时的负数处理。

2. 查询模块： 预处理完成后，每组查询直接输出预处理好的 $f[n]$ 即可，时间复杂度 $O(1)$。

该代码可高效处理 $n \leq 131072$、$Q \leq 50000$ 的数据范围，满足题目要求。