pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 $$

yukicoder No.118 門松列(2)

2変数でできることは3変数でもできそう、ということで頑張って導出した。 忘れないようにメモ。