ABC137 F - Polynomial Construction (600)
なぜACになるのかは不明
すべての$ a_iで$ a_i=0の場合、$ b_i=0になる
$ a_0=1で他は0の場合、$ b_0=1, b_{p-1}=p-1で他は0になる
$ a_i=1で他は0の場合、$ b_0=0
他の$ b_jではなぜか$ i^{j} \times x \equiv p-1 \mod pなるxで$ b_j = xとなる
複数のiで$ a_i=1となっている場合、上の結果を足し合わせても成り立つ
すべての$ (0\le i \lt p)で$ i \times x \equiv p-1 \mod pとなるxを求める
すべての$ i (0\le i,j \lt p)で$ i^{j} \times x \equiv p-1 \mod pなるxを求める
愚直に$ O(N^2 \log N)だと間に合わないが、工夫して$ O(N^2)だと間に合う
$ a_i=1となっている$ iについて足し合わした結果が答え