\[ \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X \]

の代わりに、

\[ \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X \]

の値を求め、後から \( \displaystyle \sum_{i=1}^{N} (A_i+A_i)^X \) を引いて \(2\) で割ることにします。

\[ \begin{aligned} \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X &= \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=0}^{X} \binom{X}{k}A_i^k A_j^{X-k} \\ &= \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{k=0}^{X} X! \cdot \frac{A_i^k}{k!} \cdot \frac{A_j^{X-k}}{(X-k)!} \\ &= X! \sum_{k=0}^{X} \left(\sum_{i=1}^{N} \ \frac{A_i^k}{k!}\right ) \left(\sum_{j=1}^{N} \frac{A_j^{X-k}}{(X-k)!} \right ) \end{aligned} \]

より、各 \(k\) について \( \displaystyle \sum_{i=1}^{N} \ \frac{A_i^k}{k!}\) の値を \(O(NK)\) で前計算しておくことで、各 \(X\) について \(O(K)\) で \( \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N} (A_i+A_j)^X \) の値を求めることができます。

全体の計算量は \(O(NK + K^2)\) です。 （畳み込みを用いることにより、\(O(NK + K \log K )\) で計算することもできます）