「雅礼集训 2018 Day1」树
考虑令 $f_{i,j}$ 表示大小为 $i$ 的树，深度为 $j$ 的方案数。
一般的 DP 合并过程：枚举大小为 $a,b$ 的树，然后把 $b$ 的根接到 $a$ 的根下面。但是这样会算重：打个比方，以 $1$ 为根，儿子为 $2,3$ 的树会被算两次。
不过可以发现，原树的任意一颗子树中，编号最小的点一定为根，编号次小的一定与根相连。这样只需要接入 $b$ 的时候钦定 $b$ 的根是编号次小的点即可。
不取模的答案本地用 __int128_t 或者 double 打表即可。
已经实现：提交记录
「雅礼集训 2018 Day1」仙人掌
考虑一个简单的 DP：令 $f_{i,0/1}$ 表示点 $i$ 是否被父亲的边指向时的子树方案数。这个 DP 可以用分治 NTT 优化。
现在考虑环上的情况，令 $g_{i,0/1,0/1}$ 表示环上第 $i$ 个点，上一个点到其是入边 / 出边，其到下一个点是入边 / 出边时前 $i$ 个点的方案数。只需要对子树的 $f$ 做了前缀和就可以快速转移。
最后合并给环中最上面的点即可，用分治 NTT 加速。
已经实现：提交记录
被新码风整吐了。
「雅礼集训 2018 Day1」图
以路径长度为奇数为例。
考虑前 $i$ 个点中，有 $w_0$ 个奇数白点，$w_1$ 偶数白点，$b_0$ 个奇数黑点，$b_1$ 个偶数黑点：
- 如果当前点为白点：
- 路径为奇数：
$$
2^{w_0+w_1}\sum_{i=0}^{b_0}[2\mid i]\sum_{j=0}^{b_1}{b_0\choose i}{b_1\choose j}=2^{w_0+w_1+b_0+b_1-1}
$$ -
路径为偶数：情况类似。
- 路径为奇数：
-
如果当前点为黑点：情况类似。
这样子的话可以发现，奇数路径和偶数路径的数量是相等的，正因为如此，就没必要将奇数和偶数分别记录了。接着考虑黑白点个数。容易发现上述转移式跟黑白点个数并没有关系。
最后需要注意，奇偶路径数相等，即组合数下标按照奇偶分类后和相等，对 ${n\choose m}$ 中 $n=0$ 的情况是不成立的，在这种情况下只能从偶数转移到奇数，需要单独讨论。
判断 $n=0$ 的情况只需要记录是否存在相应节点即可，注意路径数奇偶性还需要再开一维。时间复杂度 $O(n)$ 。
已经实现：提交记录
0 条评论