主要思路

这些 3000+ 题目里做过最小清新的。

首先肯定可以想到，分解质因子之后，对于一个 \(p^c\)，把每个元素该质因子的指数拿出来做中位数即为此质因子的贡献。我大概想到这里就断片了。

主要思路

首先对于 \(d = 1\)，答案就是 \(k^n\)。

对于 \(d = 2\)，其实发现可以用生成函数来直接乘：\( A(x) = \sum_{i = 0}^\infty \frac{1}{i!} x^i [2 | i] \)，那么答案就是 \( A^k(x)[x^n] \)。发现可以变通奇偶性，所以 \(A(x) = \frac{e^x + e^{-x}}{2}\)，然后试着二项式展开：

Continue reading →

推导思路

第一次坐到这种类型的题，社会社会（抱拳）。

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

Continue reading →