ARC106 D - Powers (600)
コンテスト中の考察
基本は二項分布を使って求めて計算する
後ろの方からX乗の累積和を求めておくと計算量を削減できる
$ X=1なら$ (A_1 + A_2 + A_3 + A_4) \times 3
$ X=2なら$ (A_1^2+A_2^2+A_3^2+A_4^2) \times 3 + (A_1 \times (A_2+A_3+A_4) + A_2 \times (A_3+A_4) + A_3 \times A_4) \times 2
それでもX毎に$ O(NK)、全体で$ O(NK^2)になるので間に合わない
解説の解法
$ \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X = \frac{\sum_{L=1}^{N} \sum_{R=1}^{N} (A_L+A_R)^X - \sum_{i=1}^{N-1} (A_i+A_i)^X}{2}
分解することで事前計算を$ O(NK)、本計算をX毎に$ O(K)で全体で$ O(NK + K^2)にできる
事前計算部分で毎回累乗を計算すると$ O(NK \log K)になるので事前に前回の累乗の結果を使うなどの工夫が必要