60圣晶石可以抽出学姐二宝（数列前 k 次幂和）

· · 算法·理论

如题，20抽出学姐2宝，我们要求所有 f_{1\sim m}，其中

f_k=\sum\limits_{i=1}\limits^{n}a_i^k

考虑设 f 的生成函数 F，则

F(x)=\sum\limits_{i=0}\limits^{\inf}x^i\sum\limits_{j=1}\limits^{n}a_j^i\\ =\sum\limits_{j=1}\limits^{n}\sum\limits_{i=0}\limits^{\inf}(xa_j)^i\\ =\sum\limits_{j=1}\limits^{n}\dfrac{1}{1-xa_j}\\

考虑如何把 \sum 变成 \prod，我们注意到 \ln'(1-xa_j)=\dfrac{-a_j}{1-xa_j}，则我们设

G(x)=\sum\limits_{j=1}\limits^{n}\ln'(1-xa_j)\\ =\ln'\left(\prod\limits_{j=1}\limits^{n}(1-xa_j)\right)

又知

G(x)=\sum\limits_{j=1}\limits^{n}\dfrac{-a_j}{1-xa_j}\\ =\sum\limits_{j=1}\limits^{n}\sum\limits_{i=0}\limits^{\inf}(xa_j)^i(-a_j)\\ =-\sum\limits_{j=1}\limits^{n}\sum\limits_{i=0}\limits^{\inf}x^ia_j^{i+1}

则 F(x)=-xG(x)+n，分治 ntt 算 G(x) 然后 \ln 求导即可，时间复杂度为 O(n\log^2 n)。