P5169:xtq的异或和 – 题解

主要思路

这题还挺好的。最后异或出来的路径是有链和环组成的。我们可以把链和环分开来求,因为从链上某点到环上某点之间的距离可以计算两次,所以不造成影响。所以我们可以把链做一个多项式,环做一个多项式,在做一遍 FWT_XOR 就完美了。

继续阅读P5169:xtq的异或和 – 题解

P3978:[TJOI2015]概率论 – 题解

推导思路

第一次坐到这种类型的题,社会社会(抱拳)。

先考虑怎么算分母:如果有 \(f_i\) 代表大小为 \(i\) 的树的种类数,那么可以显然得到 \(f_i = \sum_{j = 0}^{n – 1} f_j f_{n – j – 1}\)。得到这一步之后,分治 FFT?不,数据范围到达了惊人的 \(10^9\),所以分治 FFT 显然不现实。我们可以继续推:

继续阅读P3978:[TJOI2015]概率论 – 题解