P5591
zhylj
·
·
个人记录
注意到所求为：
\frac 1k\left(\sum_{i=0}^n\binom {n}{i}p^ii-\sum_{i=0}^n\binom {n}{i}p^i(i\bmod k)\right)
前者众所周知等于 np(1+p)^{n-1}，证明可以通过对 (1+x)^n = \sum \binom ni x^i 两边同时求导再乘上 x 得到。
对于后者，考虑枚举 i\bmod k=j，计算对应系数的和，即：
\sum_{i=0}^n \binom ni p^i[i\bmod k=j]
这为 (1+px)^n 所有 \bmod k 同余 j 次项系数之和，实际上就是在循环卷积意义下的快速幂，而 NTT 如果超出次数实际上就是在某个 \bmod 2^t 意义下做循环卷积，所以直接 NTT 完，每一项求个 n 次幂，再 NTT 回去就得到答案了。事实上 NTT 只需要最后一次，前面的可以直接 \mathcal O(k) 算。
时间复杂度 \mathcal O(k\log n)，直接跑了近期的最优解。
代码。