ただしO(N^2)は間に合わないものとする。
- 基本的な攻略法
- type0 明らかな場合
- type1 四則演算型
- type2 順序型
- type3 bit演算型
- type4 数論的関数型
- type5 その他
- type6 特殊な性質を持つ一般のパターン
- 最後に
基本的な攻略法
演算が交換可能かどうかで大きく変わる。$f(x,y)=f(y,x)$ならば以下の性質があるため、その性質により簡単に計算できる場合がある。
1.
$$\sum_{1\leq i\lt j\leq N}f(A_i,A_j)=\frac{1}{2}\left(\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i,A_j)\right)-\frac{1}{2}\left(\sum_{i=1}^{N}f(A_i,A_i)\right)$$
となる。前者が因数分解されてなんらかの形で簡単に計算できる場合がある。後者は何もしなくても$O(N)$である。
2.
$A_i$の順序を気にする必要がなくなる。（対称式なので）
すると
(i) $A_i$をソートした場合の答えを計算しても問題ない
(ii) $A_i=k$をみたす$i$の個数だけの情報を見ても問題ない
といった手法が使える。
演算が交換可能でない場合は、これらの手法が使えないので一般的に難しくなる。
例えば、以下のようなものですら解答を考えるのは難しいだろう。ただし不可能かどうかは断言できないので明言を避けようと思う。（もし分かる人がいたら教えてくれると嬉しいです。）
- 累乗 f(x,y)=pow(x,y)
- 割り算（小数部分切り捨て） f(x,y)=floor(y/x)
- 剰余 f(x,y)=y%x
引き算と割り算については、可換でないのに解法が比較的簡単なので、これは奇跡的と言ってもいいだろう。
（追記：floorとmodはどうやら方法があるみたいです。後述）
type0 明らかな場合
定数関数 f(x,y)=1
単純に非順序対の個数を求めれば良い。
$$\mathrm{ans}=\frac{N(N-1)}{2}$$
射影 f(x,y)=y
$$\mathrm{ans}=\sum_{i=0}^{N-1}iA_i$$
f(x,y)=xの場合も本質的に同じである。
type1 四則演算型
足し算 f(x,y)=x+y
iについてA_iが何回足されるかを考えればよい。
$$\mathrm{ans}=\sum_{i=1}^{N}(N-1)A_i$$
引き算 f(x,y)=x-y
やり方は足し算とほぼ変わらない。
$$\mathrm{ans}=\sum_{i=0}^{N-1}iA_i-(N-1-i)A_i=\sum_{i=0}^{N-1}(2i+1-N)A_i$$
掛け算 f(x,y)=xy (ABC177-C)
やり方は2通りある。
① $$\mathrm{ans}=\frac{1}{2}\left(\sum_{i=1}^{N}A_i\right)^2-\frac{1}{2}\sum_{i=1}^{N}{A_i}^2$$
とすればよい。2で割ることについては、modに対する2の逆元を掛ければよい。
②$S_k=A_1+\cdots+A_k$という累積和のリストを前計算で作って、その後に
$$\mathrm{ans}=A_2S_1+A_3S_2+\cdots+A_NS_{N-1}$$
とすればよい。
割り算(有理数) f(x,y)=y/x
ただし$x,y\neq 0$浮動小数点だと誤差でおかしくなるため出題されるとしたら有理数をmodで求めるという感じになりそう。
これは掛け算のやりかた②とほぼ同じ方法で攻略できる。つまり、
$S_k=\frac{1}{A_1}+\cdots+\frac{1}{A_k}$という累積和のリストを前計算で作って、その後に
$$\mathrm{ans}=A_2S_1+A_3S_2+\cdots+A_NS_{N-1}$$
とすればよい。
割り算（小数部分切り捨て） f(x,y)=floor(x/y)
（2021年1月1日18時36分追記）
演算が非可換であるため、初見では無理そうに見えましたが、どうやら計算量の削減ができるようです。（heno239さんありがとうございました。）
まず、BITを使うことで、[0,A_i),[A_i,2A_i),...の各区間の中にあるA_iの個数を求めて足すという発想が思い浮かふ。しかしその場合ではA_1=...=A_{n-1}=1,A_n=maxAといったケースの時に遅くなってしまう。
そこでA_iが大きい時と小さい時でやり方を変えるという方法が思い浮かぶ。
つまり、
- $A_i\lt\sqrt{\max{A}}$の部分は愚直に求める。
- $A_i\geq \sqrt{\max{A}}$の部分はBITを使って計算する
といった方法を使うと$O(N\sqrt{\max{A_i}}\log{\max{A_i}})$の計算量で計算できる。
また、割り算の順番を逆にしてもやり方は本質的に同じである。
$$\sum_{i\neq j}\lfloor \frac{A_i}{A_j}\rfloor$$
という式自体は
- 長さmaxA+1の配列Lを用意する
- 各iに対して、L[A[i]]を+1する
- 累積和Sを求める
- 各iについて、S_{(n+1)i}-S_{ni}を求めて適切な係数で足す
といったことは、調和級数の発散速度を考えると$O(N+\max{A}\log{\max{A}})$で計算することができる。
割り算を逆にしたものは
$$\sum_{i\neq j}\lfloor \frac{A_i}{A_j}\rfloor=\sum_{i\lt j}\lfloor \frac{A_i}{A_j}\rfloor+\sum_{i\lt j}\lfloor \frac{A_j}{A_i}\rfloor$$
より求めることが可能である。
剰余 f(x,y)=x%y
（2021年1月1日18時56分追記）
剰余については、floorの割り算ができればあとは本質的に同じ方法で解ける。
$$m=n\lfloor \frac{m}{n}\rfloor +m\%n$$
という等式が一般的に成り立つ。
$f(n,m)=n\lfloor \frac{m}{n}\rfloor$は普通のfloorとほぼ同じ方法で解ける。
$f(n,m)=m $についても明らかなのであとはこれらについて差分を取ればよい。
差分の2乗 f(x,y)=(x-y)^2 (ABC194-C)
2021年3月6日追記
$$\sum_{1\leq i\lt j\leq N}(A_i^2+A_j^2)-2(A_iA_j)$$
を求めればよい。
ここで、$f(x,y)=x^2+y^2$は、「$A_i\to A_i^2$と変換した場合のtype1の足し算」に対応する。また、$f(x,y)=xy$はtype1の掛け算に対応するため、それぞれを計算して足し合わせればOKである。
type2 順序型
最大値 f(x,y)=max(x,y)
ソートしても結果は同じ。ソートしたら$i\lt j$のときに$\max\{A_i,A_j\}=A_j$となるため、type0の射影と同じようになる。
最小値 f(x,y)=min(x,y)
ソートしても結果は同じ。ソートしたら$i\lt j$のときに$\min\{A_i,A_j\}=A_i$となるため、type0の射影と同じようになる。
絶対値 f(x,y)=|x-y| (ABC186-D, CODE THANKS FESTIVAL 2018-C)
ソートしても結果は同じ。ソートしたら$i\lt j$のときに$|A_j-A_i|=A_j-A_i$となるため、type1の引き算と同じになる。
type3 bit演算型
排他的論理和 f(x,y)=x xor y (ABC147-D)
ビットごとに独立で考えればよい。各bitにおいて、1が$k$個,0が$N - k$個であるとき、そのビットが答えに寄与する部分は$k(N - k)$である。あとはそれを足せば良い。
論理積 f(x,y)=x and y
xorとほぼ同じ。あるbitに対して1が$k$個,0が$N-k$個であるとき,そのbitが答えに寄与する部分は$\frac{k(k - 1)}{2}$になる。
論理和 f(x,y)=x or y
xorとほぼ同じ。あるbitに対して1が$k$個,0が$N-k$個であるとき,そのbitが答えに寄与する部分は$\frac{N(N - 1)}{2}-\frac{(N-k)(N - k - 1)}{2}$になる。
type4 数論的関数型
最小公倍数 f(x,y)=lcm(x,y) (AGC038-C)
まず、演算が交換可能であるため、
$$\sum_{i=1}^{N}\sum_{j=1}^{N}\mathrm{lcm}(A_i,A_j)$$
を求めれば十分である。
これは
$$\sum_{i=1}^{N}\sum_{j=1}^{N}\frac{A_iA_j}{\mathrm{gcd}(A_i,A_j)}$$
と等しい。
目標としては、自然数$g$に対して$g|\mathrm{gcd}(x,y)$となるような組に対する答えを高速に求めれれば良い。$g|\mathrm{gcd}(x,y)$は$g|x \land g|y$と同値である。
$B_n$を「$A_i=n$となるような$i$の個数」と定める。すると答えは
$$\mathrm{ans}=\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}\frac{B_nB_mnm}{\mathrm{gcd}(n,m)}$$
となる。ここで、
$$\sum_{d|n}w_d=\frac{1}{n}$$
となるような$w_d$を用意する。これはメビウスの反転公式(Wikipediaのリンク)を使うと具体的に構成することができる。すると、
$$\mathrm{ans}=\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}{B_nB_m}nm\sum_{d|n \land d|m}w_d$$
$$=\sum_{d=1}^{\infty}w_d\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}didjB_{di}B_{dj}$$
$$=\sum_{d=1}^{\infty}w_d\left(\sum_{i=1}^{\infty}diB_{di}\right)^2$$
これを各$d$について求めれれば良い。$A_i$の上限を$ M $とおくと、計算量は各$d$に対して$O(M/d)$なので、全体の計算量は調和級数の発散速度を考えると$O(M\log{M})$となる。
最大公約数 f(x,y)=gcd(x,y)
解き方は最小公倍数の場合とほぼ同じである。（ただしLCMsの場合と違って答えは大きくならないのでmodを取る必要はないかもしれない。）
演算が交換可能であるため前述の性質をフル活用することができる。
まず、
$$\sum_{i=1}^{N}\sum_{j=1}^{N}\mathrm{gcd}(A_i,A_j)$$
を求められればOKである。
次に、$B_n$を「$A_i=n$となる$i$の個数」と定めたとき、
$$\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}B_nB_m\mathrm{gcd}(n,m)$$
ここで、$w_n$を、今度は$\sum_{d|n}w_d=n$となるように取る。これもメビウスの反転公式によって構成できる。
$$=\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}\sum_{d|n\land d|m}B_nB_mw_d$$
$$=\sum_{n=1}^{\infty}\sum_{m=1}^{\infty}\sum_{d|n\land d|m}B_nB_mw_d$$
$$=\sum_{d=1}^{\infty}w_d\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}B_{di}B_{dj}$$
$$=\sum_{d=1}^{\infty}w_d\left(\sum_{i=1}^{\infty}B_{di}\right)^2$$
よってこれも$O(\max{A_i}\log{\max{A_i}})$で計算することができる。
type5 その他
多項式の掛け算
多項式$f_i(x)(1\leq i\leq N)$が用意されて、これについて
$$\sum_{1\leq i\lt j\leq N}f_i(x)f_j(x)$$を求めたい
これも演算は可換なのでテクニックを駆使すると、結局
$$\frac{1}{2}\left(\sum_{i=1}^{N}f_i(x)\right)^2-\frac{1}{2}\left(\sum_{i=1}^{N}f_i(x)^2\right)$$
を求めればよい。
これ以降は多項式の次数に依存する。
mod 998244353ならFFTで計算は速くなりそうではある。なにげに足し算で時間をかけてしまうため、$f_i$が全て$K$次多項式ならば計算量は$O(NK^2\log{K})$かかる。$K$が大きすぎるのは現実的ではないかも？
二項係数
さすがに$f(n,m)={}_{n}{\mathrm{C}}_{m}$ならば非可換であるためとても難しくなると思う。よってここでは
$$f(x,y)=\frac{(x+y)!}{x!y!}$$
で考えてみる。ただし、答えは大きくなるので998244353で割った余りを出力する。これも「可換ならば使えるテクニック」で
$$\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}B_nB_m\frac{(n+m)!}{n!m!}$$
となる。ただし$B_n$は$A_i=n$となる$i$の個数である。ここで、この式は
$$\sum_{n=0}^{\infty}\sum_{k=0}^{n}B_kB_{n-k}\frac{n!}{k!(n-k)!}$$
となっている。ここで、
$$F(x)=\sum_{n=0}^{\infty}\frac{B_n}{n!}x^n$$
として、
$$\left[x^n\right]F(x)^2=\sum_{k=0}^{n}B_kB_{n-k}\frac{1}{k!(n-k)!}$$
となる。*1
よって$F(x)^2$の係数をそれぞれ求めてから$n$について総和を取ればよい。
$F(x)^2$はFFTを使えば計算できるので、計算量は$O(\max{A_i}\log{\max{A_i}})$となる。
powers f(x,y)=pow(x+y,X) (ARC106-D)
これも「可換ならば使えるテクニック」を使うことができるため、以下を求めればよい。
$$\sum_{i=1}^{N}\sum_{j=1}^{N}(A_i+A_j)^X$$
結局これは展開すると以下を求めればよいことになる。
$$\sum_{i=1}^{N}\sum_{j=1}^{N}A_i^k{A_j}^{X-k}=\left(\sum_{i=1}^{N}A_i^k\right)\left(\sum_{j=1}^{N}{A_j}^{X-k}\right)$$
よって、$\sum_{i=1}^{N}A_i^k$を前計算すれば求めることができる。計算量は$O(NK+K^2)$である。ちなみにこの問題は制約が厳しいため、DPテーブルの作る際に繰り返し二乗法を使うとTLEになるかもしれないので注意である。*2
掛け算＋剰余 f(x,y)=xy mod P (AGC047-C)
「掛け算の総和の剰余」は灰diffなのに、「掛け算の剰余の総和」は橙diffになるのすごくない？
簡単に言えば、原始根でFFTをする。
手前味噌だけど解説記事
集合の定義関数 f(x,y)=1_[L,R) (x-y)
（2021年1月1日13時31分追記）
$x,y$が$x-R\lt y\leq x-L$,つまり$x-R+1\leq y\lt x-L+1$のときだけ1で、それ以外の場合は0になる。よって
- 長さmaxAのBIT（またはセグメントツリー）を作成する
- 各iに対して、以下の操作をする
- A_iに1を追加する
- [x-R+1,x-L+1)における区間和を足す（BITなので高速にできる）
によって解ける。ここで、L=1,R=∞ならばこれは転倒数となる。
桁和 f(x,y)=(x+y)の桁和 (ARC158-C)
2023年3月13日追記
で解説した
足したあと割る f(x,y)=floor((x+y)/M),(x+y) %M
2023年3月13日追記
上記の桁和の場合を計算する過程で使う。上記記事の途中で解説したのでリンク参照
type6 特殊な性質を持つ一般のパターン
変数分離型 f(x,y)=g(x)h(y)
（2021年1月1日19時05分追記）
$f(x,y)=g(x)h(y)$と変数分離できると仮定する。
このとき、
$$S_k=g(A_1)+\cdots+g(A_k)$$
となる。よって答えは
$$\mathrm{ans}=S_1h(A_2)+\cdots+S_{N-1}h(A_N)$$
となる。
和の関数型 f(x,y)=g(x+y)
（2021年1月1日19時05分追記）
$f(x,y)=g(x+y)$という形で書けると仮定する。このとき、演算は可換なのでいつものテクニックが使える。$B_n$を「$A_i=n$となる$i$の個数」と定めると、答えは
$$\mathrm{ans}=\sum_{i=0}^{\max{A}}\sum_{j=0}^{\max{A}}B_iB_jf(i+j)$$
$$\mathrm{ans}=\sum_{n=0}^{2\max{A}}f(n)\sum_{k=0}^{n}B_kB_{n-k}$$
となる。ここで、各$n$に対する$\sum_{k=0}^{n}B_kB_{n-k}$についてはFFTを用いれば$O(\max{A}\log{\max{A}})$で計算することができる。よってこれらの値を愚直に足し合わせれば$O(\max{A}\log{\max{A}})$で計算することが可能である。
A_iの値の範囲が狭い＆演算が可換のとき
（2021年3月6日追記）
$A_i$の値の範囲を$L\leq A_i\leq R$とする。このとき、$O((R-L)^2)$が十分小さい場合は、関数がどのようなものでも求めることができる。
$B_i$を「$A_k=i$となる$k$の個数」とおく。
演算は可換であるため、性質1を使うと
$$\sum_{i=1}^{N}\sum_{j=1}^{N}f(A_i,A_j)$$
を求めればよいことになる。ここで、これは
$$\sum_{i=L}^{R}\sum_{j=L}^{R}B_iB_jf(i,j)$$
となる。これを愚直に求めればOKである。
最後に
既に世に出ている問題で、他にもあったら教えてください。
