标签：P5333 limits JSOI2019 sum 一棵树 times 神经网络 EGF dp

P5333 [JSOI2019]神经网络

Solution

EGF 表示有标号排列。

对每棵树分别算出划分成 \(i\) 条链的方案数，记为 \(f_i\)。

具体地：设 \(dp[u][i][0/1/2]\) 表示在 \(u\) 子树内拆分成 \(i\) 条已结束的链，

\(0\): 已拼完，无法再延伸

\(1\): 单点，可继续向上扩展

\(2\): 长度 \(>1\) 的链，且可继续向上扩展 (为了处理正反向方案数 \(\times 2\) 的问题)

对于根节点视作它可以向父节点扩展，即和其它节点同等处理

状态由划分的客观形态决定 不能对 \(1/2\) 情况人为钦定为 \(0\)

\(f_i = dp[root][i][0] + dp[root][i - 1][1] + 2 \times dp[root][i - 1][2]\)

\(dp\) 转移有点繁复，但写出来极度舒适

把所有链拼成一个路径排列，则相邻的链颜色不同。

对于其他树，EGF 为：（采用容斥思想，枚举相邻位置个数）

\[\sum\limits_{i = 1}^{k}f_i\times i! \times \sum\limits_{j = 0}^{i - 1}(-1)^{j}\binom{i - 1}{j}\frac{x^{i - j}}{(i - j)!} \]

对于第一棵树，第一条链被固定为起点，且第一棵树最后一条链不能与第一条链相邻。

第一条链被固定为起点：但统计一号点不必作为排列的起点，只需平移即可得到合法哈密顿回路。

第一棵树最后一条链不能与第一条链相邻：可以把两条链拼起来看成第一棵树的另一种拆分方案，因此存在计重问题。

在前一个限制下，用任意合法方案减去强行钦定首尾同色的合法方案，得到第一棵树的 EGF：

\[\sum\limits_{i = 1}^{k}f_i\times (i - 1)! \times \sum\limits_{j = 0}^{i - 1}(-1)^{j}\binom{i - 1}{j}\frac{x^{i - j - 1}}{(i - j - 1)!} - \sum\limits_{i = 1}^{k}f_i\times (i - 1)! \times \sum\limits_{j = 0}^{i - 1}(-1)^{j}\binom{i - 1}{j}\frac{x^{i - j - 2}}{(i - j - 2)!} \]

注意后者最后一条链的选取有 \(i - 1\) 种方案，因此其前面的系数仍为 \((i - 1)!\) 而非 \((i - 2)!\)。

暴力卷积，最后把每一项的系数乘对应的阶乘（化成 EGF 的形式）。

标签：P5333,limits,JSOI2019,sum,一棵树,times,神经网络,EGF,dp
From： https://www.cnblogs.com/Schucking-Sattin/p/17462932.html