简述
在计数题解题中遇到要求 \(x \bmod m = 0\) 的条件时,如果式子的计算复杂度比较高,但是式子里含有二项式系数的时候,就可以考虑用单位根反演。
第一次坐到这种类型的题,社会社会(抱拳)。
先考虑怎么算分母:如果有 \(f_i\) 代表大小为 \(i\) 的树的种类数,那么可以显然得到 \(f_i = \sum_{j = 0}^{n – 1} f_j f_{n – j – 1}\)。得到这一步之后,分治 FFT?不,数据范围到达了惊人的 \(10^9\),所以分治 FFT 显然不现实。我们可以继续推: