【YBT2022寒假Day3 A】森林之和(prufer序列)(DP)
森林之和
题目链接:YBT2022寒假Day3 A
题目大意
求对于 n 个有编号点构成的森林,求每种森林每个点度数的平方和的和。
思路
我们看到有有关所有编号树,不难想到 prufer 序列和矩阵树。
那这里应该就是利用 prufer 序列来 DP 答案。
但它是森林,那我们考虑先求出构造一棵树的,然后再依次把树放在一起。
那根据 prufer 序列的性质我们可以知道构造一棵树大小为
x
x
x 的方案数
f
x
=
x
x
−
2
f_x=x^{x-2}
fx=xx−2。
那接着就是森林的(
g
x
g_x
gx),那我们要记得每次选新的数要固定
1
1
1 点在里面,这样就不会有出现重复的。
然后你考虑枚举每次放进去的树的大小:
g
x
=
∑
i
=
1
x
g
x
−
i
f
i
(
x
−
1
i
−
1
)
g_x=\sum\limits_{i=1}^{x}g_{x-i}f_i\binom{x-1}{i-1}
gx=i=1∑xgx−ifi(i−1x−1)
然后就是计算贡献,你会发现其实每个点的期望贡献是一样的,那我们只需要求出一个,答案乘 n n n 就可以了。
那首先我们求一棵树中一个点的期望贡献
p
x
p_x
px,考虑枚举它的度数。(度数
0
0
0 没有贡献就省去了)
p
x
=
∑
i
=
1
x
−
1
i
2
(
x
−
2
i
−
1
)
p_x=\sum\limits_{i=1}^{x-1}i^2\binom{x-2}{i-1}
px=i=1∑x−1i2(i−1x−2)(这里也固定了
1
1
1)
那这样我们就可以求森林中一个点的期望贡献
w
x
w_x
wx 了,也是类似计算个数的方法,枚举新加子树大小。(也要固定)
w
x
=
∑
i
=
1
x
w
x
−
i
p
i
(
x
−
1
i
−
1
)
w_x=\sum\limits_{i=1}^{x}w_{x-i}p_i\binom{x-1}{i-1}
wx=i=1∑xwx−ipi(i−1x−1)
然后答案数组就是 w x w_x wx 了。
代码
#include<cstdio>
#define ll long long
#define rr register
#define C(x, y) C[x][y]
using namespace std;
int T, n;
ll mo, p[5001], w[5001], f[5001], g[5001];
ll C[5001][5001];
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo;
y >>= 1;
}
return re;
}
int main() {
// freopen("forest.in", "r", stdin);
// freopen("forest.out", "w", stdout);
scanf("%d %lld", &T, &mo);
C[0][0] = 1;
for (rr int i = 1; i <= 5000; i++)
for (rr int j = 0; j <= i; j++)
C[i][j] = (C[i - 1][j] + (j ? C[i - 1][j - 1] : 0)) % mo;
f[0] = f[1] = 1;
for (rr int i = 2; i <= 5000; i++)
f[i] = ksm(i, i - 2);
g[0] = g[1] = 1;
for (rr int i = 2; i <= 5000; i++) {
ll tmp = ksm(i - 1, i - 1), ww = ksm(i - 1, mo - 2);
for (rr int j = 1; j <= i; j++) {
(g[i] += g[i - j] * f[j] % mo * C(i - 1, j - 1) % mo) %= mo;
if (i == j) break;
tmp = tmp * ww % mo;
(p[i] += j * j % mo * C(i - 2, j - 1) % mo * tmp % mo) %= mo;
}
for (rr int j = 1; j <= i; j++)
(w[i] += C(i - 1, j - 1) * p[j] % mo * g[i - j] % mo) %= mo;
}
while (T--) {
scanf("%d", &n);
printf("%lld\n", w[n] * n % mo);
}
return 0;
}
相关文章
- 动手学深度学习实践—文献阅读(双头序列到序列(attention)插补水质模型dual-SSIM)
- 时间序列-预测-模型:LSTM【单特征/多特征】【利用前50个时间步的数值预测接下来的10个时间步的数值:(0-49)->50;(1-50此50为上一步预测出的)->51;(2-51)->52...】
- 子序列的和
- 819.递增序列
- LeetCode·每日一题·801.使序列递增的最小交换次数·动态规划
- CF417D--- Cunning Gena(序列+像缩进dp)
- 《生物序列分析》
- P4387 P4387 【深基15.习9】验证栈序列
- 【51nod 1202】子序列个数(DP)
- [LintCode] 619 Binary Tree Longest Consecutive Sequence III 二叉树最长连续序列 III
- 【找到和最大的长度为 K 的子序列(2099-java)】