俗に積の和典型と呼ばれる考え方を紹介します．

\(K\) 個の選んだボールを固定したとき，以下が成立します．

選んだ \(K\) 個のボールから一つを選び青い印を付ける．同様に一つを選び赤い印を付ける．（ここで同じボールに青い印と赤い印を付けてもよい．）このような印の付け方は \(K^2\) 通りあるが，その全てに対する

• 赤い印の付いたボールに書かれた数 \(\times\) 青い印の付いたボールに書かれた数

の総和がその選び方のスコアと一致する．

この言い換えを説明します．選んだボールに書かれた数が順に \(B_1,\ldots,B_K\) とするとき，スコアが \((B_1+\ldots+B_K)\times (B_1+\ldots+B_K)\) と書けます．この式を展開することを考えると，青い印を付けることが左の括弧から一つ選ぶこと，赤い印を付けることが右の括弧から一つ選ぶことと対応しています．このような考え方が積の和典型と呼ばれていると筆者は認識しています．

ここまでくれば後は容易です．青い印と赤い印を同じボールに付ける場合，青い印と赤い印を別のボールに付ける場合を別々に考えます．

ボール \(i\) に青い印と赤い印を付けるとき，そのような付け方があり得るボール \(K\) 個の選び方は \(\binom{N-1}{K-1}\) です．（ボール \(i\) は当然選ばないといけないので）

よってボール \(i\) に青い印と赤い印を付けるときの寄与は \(A_i^2\binom{N-1}{K-1}\) です．これを全ての \(i\) で足し合わせるのは \(\mathrm{O}(N)\) で行えます．

ボール \(i\) に青い印，ボール \(j\ (i\neq j)\) に赤い印を付ける場合を考えます．そのような付け方があり得るボール \(K\) 個の選び方は \(\binom{N-2}{K-2}\) です．（ボール \(i,j\) は当然選ばないといけないので）

よってボール \(i\) に青い印，ボール \(j\ (i\neq j)\) に赤い印を付けるときの寄与は \(A_iA_j\binom{N-2}{K-2}\) です．これを全ての \(i,j\ (i\neq j)\) で足し合わせればよく，結局

\[\sum_{i\neq j} A_i A_j\]

を求める問題になります．これは \((\sum_{i=1}^N A_i)^2 - \sum_{i=1}^N A_i^2 \) と一致するので \(\mathrm{O}(N)\) で計算できます．