P7275 计树

251Sec · 2025-06-25 08:34:09 · 题解

通过找规律，发现 f(n) 满足如下关系式：

据此计算即可，复杂度 O(n)，可以优化到 O(\log n)。

核心代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 998244353;
int n;
ll f[100005];
ll QPow(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P;
    return res;
}
int main() {
    scanf("%d", &n);
    f[1] = 0, f[2] = QPow(n, P - 2) * 2 % P, f[3] = QPow(n, P - 2) * 3 % P, f[4] = 4;
    for (int i = 5; i <= n; i++) f[i] = (f[i - 1] * 2 + f[i - 2] * (2 * n - 3) + f[i - 3] * (2 - n) - f[i - 4]) % P;
    printf("%lld\n", (f[n] + P) % P);
    return 0;
}

首先有一个基本的想法：钦定若干连续段，然后把它们拼成一棵树。显然这会算重，于是给每个连续段赋一个容斥系数，这可以暴力推出来，至此我们得到 O(n^2) 的 DP。

我们猜测：在 n 固定时，DP 数组有较短的递推式，且递推式的每一项系数是关于 n 较简单的式子，使用 BM 打表即可。