CF100965C题解..

求方程

\[ \begin{array}\\ \sum_{i=1}^n x_i & \equiv & a_1 \pmod{p} \\ \sum_{i=1}^n x_i^2 & \equiv & a_2 \pmod{p} \\ & \vdots & \\ \sum_{i=1}^n x_i^n & \equiv & a_n \pmod{p}\end{array} \]

的解,或输出"NO".

题解

构造多项式\(\prod_i (x-x_i)\),逐位确定.

把我刚才说的那个多项式拆开,然后发现那个系数可以通过a_n容斥出来.

具体的, a_1, (a_1^2-a_2)/2, ..., 你可以看到这些就是k个不同的x_i的积的和.

题目中似乎漏条件了: p是素数.

上一篇:2016ACM青岛区域赛题解


下一篇:The trouble of Xiaoqian