专栏文章

P7275 计树

2251Sec
P7275题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip1ipxb
此快照首次捕获于
2025/12/03 04:38
3 个月前
此快照最后确认于
2025/12/03 04:38
3 个月前
查看原文
通过找规律，发现 f(n)f(n) 满足如下关系式：
f(1)=0f(1)=0 f(2)=2nf(2)=\frac{2}{n} f(3)=3nf(3)=\frac{3}{n} f(4)=4f(4)=4 f(i)=2f(i−1)+(2n−3)f(i−2)+(2−n)f(i−3)−f(i−4)f(i)=2f(i-1)+(2n-3)f(i-2)+(2-n)f(i-3)-f(i-4)
据此计算即可，复杂度 O(n)O(n)，可以优化到 O(log⁡n)O(\log n)。
核心代码：
CPP
#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(n2)O(n^2) 的 DP。
我们猜测：在 nn 固定时，DP 数组有较短的递推式，且递推式的每一项系数是关于 nn 较简单的式子，使用 BM 打表即可。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...