$\sum_{i=0}^{N-2}\sum_{j=i+1}^{N-1} f(A_i, A_j)$ の計算はさまざまな典型の宝庫

外部の記事

• N 個の整数 A_1,A_2,…,A_N が与えられ、N⋅(N−1)/2 個すべての非順序対 (Ai,Aj) (i<j) に対するf(A_i, A_j)の和を求める問題 - shakayamiの日記
• Typical Problems of Sums ver2 (Twitter) Typical Problems of Sums ver2
• Typical Problems of Sums (Twitter)

一般論

• 0オリジンで考えた場合の絵

  

• $f(x, y) = f(y, x)$ ($f$ が可換) の場合

  • $(A_i)_i$ の順番を入れ替えて良い
    • 例えばソートしてもよい
  • (正方形-対角線)/2 という計算ができる

• $(N-1) \sum_{i=0}^{N-1} A_i$ みたいな $\mathrm{O}(N^2 \max A_i)$ くらいの値の計算をすると64bit符号付き整数（最大 $9.2\times10^{18}$ くらい）でオーバーフローが発生することがある

  • 例えば $N\leq 10^5, A_i \leq 10^9$ みたいな場合、総和は $10^{19}$ くらいになってしまう。
  • $N \leq 3\times 10^5, A_i \leq 10^8$ みたいな場合であれば、総和は $9\times 10^{18}$ になってぎりぎり大丈夫

• 線形性

  • 大事

各論

■ 定数関数 $f(x,y) = 1$

答え: $N(N-1)/2$

■ 射影 $f(x,y) = x$

答え: $\sum_{i=0}^{N-1} (N-1-i) A_i$