Mod P Sum

解説

$\displaystyle \sum^{i<j}(A_i+A_j)^p$ の値をそのまま求めようとすると、$_nC_2$ 通りを全探索する必要があるため累乗計算を含めて $O(N^2\log p)$ かかり実行時間制限に間に合いません。よって、計算量の改善を考えます。

ここで、$(A_i+A_j)^p$ を変形してみます。

$\displaystyle (A_i+A_j)^p = \sum_{k=0}^{p} \begin{pmatrix}p\\k\end{pmatrix}A_i^{p-k}A_j^k$ この値は、$k=0,p$ のときそれぞれ $A_i^p,A_j^p$ となり、 $k$ の値がそれ以外のときは二項係数の素因数に必ず $p$ を含むため $p$ の倍数になります。 よって、$\displaystyle \sum^{i<j}(A_i+A_j)^p \equiv\displaystyle \sum^{i<j}(A_i^p+A_j^p)$ $(mod \ p)$

が成り立ちます。ここで、$A_i^p$ は、この和の中に $N-1$ 回出てくるため、$\displaystyle \sum^{i<j}(A_i^p+A_j^p) = (N-1)\sum_{i=1}^{N}A_i^{p}$ です。

したがって、答えは $(N-1)\sum_{i=1}^{N}A_i^{p}$ を $p$ で割った余りとなります。時間計算量は累乗計算を含めて $O(N \log p)$ であり、実行時間制限に間に合います。よって、この問題を解くことができました。

追記

$\displaystyle \sum^{i<j}(A_i+A_j)^p \equiv\displaystyle \sum^{i<j}(A_i^p+A_j^p)$ $(mod \ p)$　の変形は、１年生の夢 と呼ばれる実数範囲では成り立たない等式 $(a+b)^p = a^p + b^p$ が本当に成り立ってしまうケースです。この等式は $p$ が素数であり、かつ $mod \ p$ の世界であれば成り立つことが知られています。