山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

重要なシグマ計算 [競技プログラミング]

二重シグマの計算

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

感想

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