アレが出てきた…！
なんとかコンテスト中に通せたので良かった。
問題概要
$f(x,y)$を$x+y$の桁和とする。このときに$\sum_{i,j} f(A_i,A_j)$を解けるだろうか？ただし$O(N^2)$は間に合わないよ
解法
まず、以下の等式が成り立つ
$$f(x)=x-9\sum_{n=1}^{\infty}\lfloor \dfrac{x}{10^n}\rfloor$$
$n$についての無限和になっているけど、実際には$x\geq 10^n $となるような範囲の$n$だけ計算すればOK
今回の場合$A_i+A_j\leq 2\times 10^{15}$なので$n\leq 16$まで計算すればOK
つまり、求める式はこうなる
$$\sum_{i=1}^{N}\sum_{j=1}^{N} (A_i+A_j)-9\sum_{n=1}^{\infty}\sum_{i=1}^{N}\sum_{j=1}^{N}\lfloor \dfrac{A_i+A_j}{10^n}\rfloor$$
ここで、
$$\sum_{i=1}^{N}\sum_{j=1}^{N} (A_i+A_j)=2N\sum_{i=1}^{N}A_i$$
なのでこの部分は$O(N)$で計算できる。
結局、以下の式を計算できればOK
$$F(M):=\sum_{i=1}^{N}\sum_{j=1}^{N}\lfloor \dfrac{A_i+A_j}{M}\rfloor$$
ところで、
$$G(M):=\sum_{i=1}^{N}\sum_{j=1}^{N}(A_i+A_j)\mod M $$
という式において、
$M\lfloor x/M\rfloor +(x\mod M)=x$なので、
$$F(M)=\dfrac{1}{M}\left(2N\sum_{i=1}^{N} A_i - G(M)\right)$$
である。
よって、$G(M)$が計算できればOKである。
ここで、
$$G(M)=\sum_{i=1}^{N}\sum_{j=1}^{N} (A_i+A_j)\mod M $$
について、
$$G(M)=\sum_{i=1}^{N}\sum_{j=1}^{N} ( (A_i\mod M)+(A_j\mod M) )\mod M $$
が成立する。よって$A_i \leftarrow A_i\mod M $と変換してから計算し直しても問題ない。
以下、$A_i$を$A_i\mod M $に変換したものとして書く。つまり、$0\leq A_i\lt M $である。
このとき、$(A_i+A_j)\mod M $は$A_i+A_j$または$A_i+A_j-M $と等しくなる。これは$0\leq A_i+A_j\lt 2M $より成り立つ。また、$(A_i+A_j)\mod M=A_i+A_j-M $となるのは$(A_i+A_j)\geq M $となるようなときである。
つまり、
$$G(M)=2N\sum_{i=1}^{N}A_i - M \#\{(i,j);A_i+A_j\geq M \}$$
となる。
問題は
$$\#\{(i,j);A_i+A_j\geq M \}$$
（つまり、$A_i+A_j\geq M $となるような$(i,j)$の組の個数）
をどう求めるかである。
結論から言うと、以下の方法を使えば$O(N\log{N})$で計算できる。
0. （ $A$の全要素を$M $で割ったあまりに変換したとする）
1. $A$を$A_i \mod M $でソートする。
2.i=1,...,Nについて以下の操作をする
$A_k\geq M-A_i$となるような最小の$k$を二分探索で探す。$i$に対して$j=k,k+1,k+2,...,N$のときだけ$A_i+A_j\geq M $となるのでその分を答えに加算する
以上の方法によって答えを計算することができた。
実装例
コードの中にsolve_naive,G_naive関数がありますが、それは$O(N^2)$解で愚直に計算したもので、ランダムテストケースで合致するかでデバッグを行っています。
