重要なシグマ計算 [競技プログラミング] - ヤマカサのプログラミング勉強日記

二重シグマの計算

yukicoderの問題を解説しているサイトでシグマ計算の重要な公式を知りました。

pekempey.hatenablog.com

公式

$\displaystyle{ S = \sum_{1 \leq i \lt j \leq n} a_ia_j = \dfrac{S_n^2 - S_n^{(2)}}{2}}$

$S_n = a_1 + a_2 + \cdots + a_n$

$S_n ^{(2)}= a_1^2 + a_2^2 + \cdots + a_n^2$

確認

$\displaystyle S = \begin{bmatrix} a_1 & a_2 & \cdots & a_{n - 1} \end{bmatrix} \begin{bmatrix} a_2 + \cdots + a_n\\ a_3 + \cdots + a_n \\ \vdots \\ a_n \end{bmatrix}$

$\displaystyle = S_n^2 - \begin{bmatrix} a_1 & a_2 & \cdots & a_n \end{bmatrix} \begin{bmatrix} a_1\\ a_1 + a_2 \\ \vdots \\ a_1 + a_2 + \cdots + a_n \end{bmatrix}$

$\displaystyle 2S = 2S_n^2 - S_n^{(2)} - \begin{bmatrix} a_1 & a_2 & \cdots & a_{n} \end{bmatrix} ( \begin{bmatrix} a_1 \\ a_1 \\ a_1 \\ \vdots \\ a_1 \end{bmatrix} + \begin{bmatrix} 0 \\ a_1 \\ a_1 \\ \vdots \\ a_1 \end{bmatrix} + \begin{bmatrix} 0 \\ a_2 \\ a_2 \\ \vdots \\ a_2 \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ a_2 \\ \vdots \\ a_2 \end{bmatrix} + \cdots$

$\displaystyle + \begin{bmatrix} 0 \\ 0 \\ \vdots \\ a_{n - 1} \\ a_{n - 1} \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ a_{n - 1} \end{bmatrix} + \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ a_{n} \end{bmatrix}$ )

$\displaystyle = S_n^2 - S_n^{(2)}$

したがって、 $\displaystyle{ S = \sum_{1 \leq i \lt j \leq n} a_ia_j = \dfrac{S_n^2 - S_n^{(2)}}{2}}$

感想

正しい証明の仕方が分かんないです。