2020-team12-037

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-W9standing.png, 1000px)]]
[[Image(2021-W9submissions1.png, 1000px)]]
[[Image(2021-W9submissions2.png, 1000px)]]




== 问题 ==

whn读题还是觉得没完全注意集中，拼错了Fake news（以后用复制！），甚至把within的词语含义读错了（记住是小于等于，不是等于！）
szb想到prufer序列没有深入研究性质……
ctcB题签到出了失误


== 题解 == 

A: 花式打表

B: 签到

C: 点分治，浙江队的数据结构能力一定是可以的！

D: 打表发现只有1和24是，然而拼错了Fake news一次。。

E: 魔幻题，待补

F: 魔幻题，待补

G: 魔幻题，待补

H: 分行考虑，对于第i行，(ki,i)与(ki+1,i)会成为答案。要统计1-k对i取模结果为0和1的数目，类似于

I: 核心是prufer序列： n节点，标号不同的树总共有n^(n-2)^棵；一棵树如果节点u度数为deg,则prufer序列中u会出现deg-1次。
记f(n)为“n节点标号不同森林的数目” ,g(n）为“n节点标号不同森林的答案”，b(n)表示“n节点树的个数”， a(n)表示“n节点树的答案”。
则可以推出： b(n) = n^(n-2)^, f(n) = sum(k=0到n-1)(C(n-1,k)*b(k+1) * f(n-k-1))（每次从1到n-1选k个节点和第n个节点组成新的树）
a(n）=sum(k=1到n) C(n-2,k-1)*n*(n-1)^(n-k-1)*n*n（枚举每种度数k，则需要为prufer序列选择k-1个位置填上一个数，其他位置随意填的方案数）
最后算g(n)有两种方法：
szb: 考虑有k个节点的树的贡献为a(k) * f(n-k)*C(n,k)，直接合并即可。
whn: 仍然考虑每次用i-1个节点和第n个节点组成，那么每加入一个节点答案就是（新树数量*森林答案+新树答案*森林数量）
g[k] = add(g[k],1ll*c[k-1][i]*add(1ll*f[k-i-1]*a[i+1]%mo,1ll*g[k-i-1]*b[i+1]%mo)%mo);
注意g[0] = 0, a[0] = 0,b[0] = f[0] = 1.

J: 阅读理解，读了20分钟题以后写个跑N次的暴力即可。

[/wiki/2020-team12 返回]

问题

whn读题还是觉得没完全注意集中，拼错了Fake news（以后用复制！），甚至把within的词语含义读错了（记住是小于等于，不是等于！）

szb想到prufer序列没有深入研究性质……

ctcB题签到出了失误

题解

A: 花式打表

B: 签到

C: 点分治，浙江队的数据结构能力一定是可以的！

D: 打表发现只有1和24是，然而拼错了Fake news一次。。

E: 魔幻题，待补

F: 魔幻题，待补

G: 魔幻题，待补

H: 分行考虑，对于第i行，(ki,i)与(ki+1,i)会成为答案。要统计1-k对i取模结果为0和1的数目，类似于

I: 核心是prufer序列： n节点，标号不同的树总共有n(n-2)棵；一棵树如果节点u度数为deg,则prufer序列中u会出现deg-1次。

记f(n)为“n节点标号不同森林的数目” ,g(n）为“n节点标号不同森林的答案”，b(n)表示“n节点树的个数”， a(n)表示“n节点树的答案”。

则可以推出： b(n) = n(n-2), f(n) = sum(k=0到n-1)(C(n-1,k)*b(k+1) * f(n-k-1))（每次从1到n-1选k个节点和第n个节点组成新的树）

a(n）=sum(k=1到n) C(n-2,k-1)*n*(n-1)^(n-k-1)*n*n（枚举每种度数k，则需要为prufer序列选择k-1个位置填上一个数，其他位置随意填的方案数）

最后算g(n)有两种方法：

szb: 考虑有k个节点的树的贡献为a(k) * f(n-k)*C(n,k)，直接合并即可。

whn: 仍然考虑每次用i-1个节点和第n个节点组成，那么每加入一个节点答案就是（新树数量*森林答案+新树答案*森林数量）

g[k] = add(g[k],1ll*c[k-1][i]*add(1ll*f[k-i-1]*a[i+1]%mo,1ll*g[k-i-1]*b[i+1]%mo)%mo);

注意g[0] = 0, a[0] = 0,b[0] = f[0] = 1.

J: 阅读理解，读了20分钟题以后写个跑N次的暴力即可。

附加文件