题解：n个点有标号毛毛虫树计数

一、问题定义

$n$ 个点的有标号毛毛虫树是满足以下条件的树：存在一条树链（称为“主链”），使得所有节点到这条链的距离最多为 $1$。要求计算这类树的数量，答案对 $998244353$ 取模。

二、核心思路

毛毛虫树的结构特征是“主链 + 叶子”：所有节点要么在主链上，要么是主链上某个节点的直接邻居（叶子）。基于此，我们可以通过枚举主链长度，结合组合计数和幂运算推导公式，最终高效计算答案。

关键观察

1. 主链的选择：主链是一条有标号的树链，长度为 $k$（节点数 $1 \leq k \leq n$）。

   • 当 $k=1$：主链为单个节点，所有其他节点都是该节点的叶子（星形结构）。
   • 当 $k \geq 2$：主链为 $k$ 个节点构成的路径，剩余 $n-k$ 个节点为叶子，每个叶子可连接到主链上任意节点。

2. 无重复计数：每个毛毛虫树对应唯一的“极大主链”（无法延长的主链），避免重复统计。最终推导得出简化公式：

   • 当 $n=1$ 时，答案为 $1$；
   • 当 $n \geq 2$ 时，答案公式为：$$\text{ans}(n) = (n-1) \cdot 2^{n-1} + \sum_{k=2}^{n-1} \binom{n}{k} \cdot (k-1)! \cdot k^{n-k} $$进一步优化后，可通过预处理阶乘、逆阶乘、幂数组，在 $O(n \log n)$ 时间内计算。

公式简化与优化

通过组合数学推导，最终简化为更高效的形式（避免枚举求和，适用于 $n \leq 10^5$）：

$$\text{ans}(n) = \begin{cases} 1 & n=1, \\ (n-1) \cdot 2^{n-1} + \binom{n}{2} \cdot 2^{n-2} + \sum_{k=3}^{n-1} \binom{n}{k} \cdot (k-1)! \cdot k^{n-k} & n \geq 3, \\ 1 & n=2. \end{cases} $$

但实际工程中，通过预处理阶乘和幂数组，直接枚举 $k$ 计算求和项更易实现，且时间复杂度为 $O(n \log n)$，可满足 $n \leq 10^5$ 的要求。

预处理内容

1. 阶乘与逆阶乘：快速计算组合数 $\binom{n}{k}$。
2. 幂数组：预处理 $2^m$ 和 $k^m$（通过快速幂批量计算）。

三、代码实现

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

const int MOD = 998244353;
const int MAXN = 1e5 + 10;

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

// 快速幂
long long qpow(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    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;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init_fact();
    init_pow2();
    
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    if (n == 2) {
        cout << 1 << '\n';
        return 0;
    }
    
    long long ans = (1LL * (n-1) * pow2[n-1]) % MOD;
    for (int k = 2; k <= n-1; k++) {
        long long c = comb(n, k);
        long long fact_k_1 = fact[k-1];  // (k-1)!
        long long pow_k = qpow(k, n - k);  // k^(n-k)
        long long term = c * fact_k_1 % MOD;
        term = term * pow_k % MOD;
        ans = (ans + term) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

四、代码说明

1. 预处理模块：

   • init_fact()：预处理阶乘和逆阶乘，用于快速计算组合数 $\binom{n}{k}$。
   • init_pow2()：预处理 $2$ 的幂次，优化公式中 $2^{n-1}$ 等项的计算。
   • qpow()：快速幂函数，用于计算 $k^{n-k}$ 等幂次项，时间复杂度 $O(\log (n-k))$。

2. 核心计算：

   • 对于 $n \geq 3$，先计算基础项 $(n-1) \cdot 2^{n-1}$，再枚举主链长度 $k$ 从 $2$ 到 $n-1$，累加每个 $k$ 对应的方案数（组合数 $\times (k-1)! \times k^{n-k}$）。
   • 所有计算均对 $998244353$ 取模，避免溢出。

该代码时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$，可高效处理 $n \leq 10^5$ 的数据。