yukicoder No.118 門松列(2)
問題文
http://yukicoder.me/problems/221
解法
Ai の最大値が 100 なので簡単。
$$ \sum_{1 \le i \lt j \lt k \le n} a_i a_j a_k = \frac16 (S_1^3-3S_1 S_2 + 2S_3) $$ $$ S_1 = a_1 + a_2 + a_3 + \cdots + a_n $$ $$ S_2 = a_1^2 + a_2^2 + a_3^2 + \cdots + a_n^2 $$ $$ S_3 = a_1^3 + a_2^3 + a_3^3 + \cdots + a_n^3 $$
が成り立つので、O(n) でも解ける。
2変数の方は有名。
$$ \sum_{1 \le i \lt j\le n} a_i a_j = \frac12 (S_1^2-S_2) $$ $$ S_1 = a_1 + a_2 + a_3 + \cdots + a_n $$ $$ S_2 = a_1^2 + a_2^2 + a_3^2 + \cdots + a_n^2 $$
2変数でできることは3変数でもできそう、ということで頑張って導出した。
忘れないようにメモ。
