No.1145 Sum of Powers

$ S_K:=\sum_{i=1}^N A_i^Kとする。

$ \sum_{i=0}^\infty S_ix^i

$ =\sum_{i=1}^N \frac{1}{1-A_ix}

$ =\frac{\sum_{i=1}^N \prod_{k\neq i} (1-A_kx)}{\prod (1-A_ix)}

$ f_i:=1-A_i とする。$ \sum_{i=1}^N \prod_{k\neq i} f_i=[y] \prod_i(y+f_i) であるから分母分子ともに分割統治法で求まる。

多点評価の転置だから、Tellegan's principle によって求めることもできる。