简述
在计数题解题中遇到要求 \(x \bmod m = 0\) 的条件时，如果式子的计算复杂度比较高，但是式子里含有二项式系数的时候，就可以考虑用单位根反演。
第一次坐到这种类型的题，社会社会（抱拳）。
先考虑怎么算分母：如果有 \(f_i\) 代表大小为 \(i\) 的树的种类数，那么可以显然得到 \(f_i = \sum_{j = 0}^{n – 1} f_j f_{n – j – 1}\)。得到这一步之后，分治 FFT？不，数据范围到达了惊人的 \(10^9\)，所以分治 FFT 显然不现实。我们可以继续推：
按照多项式求逆中倍增的思想，可以写出这样的推导：假设我们已知在\(\pmod {x^{\lceil \frac{n}{2} \rceil}}\)求得\(B'(x)\)为当前的解，现在要步进至\(\pmod x^n\)，那么我们可以写出
最近懒死了，所以没有更新太多博客。在这里做一个小的集合吧。
忘了写题解，但总觉得要写点啥，所以就有了这篇题集。
无论你再怎么觉得稳，比赛完了之后仍会挂分，而且你会发现稍稍改下就他妈可以加几十分。这就是生活。
kal0rona