公式解説の後半部分において、\(k=0,1,2,\cdots\) について \(A_i + B_j+1 = k\) となる \((i, j)\) の組の個数を求めればよいです。

\(A_i, B_i\) が求まっていれば、高速フーリエ変換（FFT）を用いれば \(A_i + B_j+1\) の個数の分布を求めることができます。

具体的には次のようにします。

• 長さ \(N_1\) の数列 \(X = (X_0, X_1, \cdots, X_{N_1-1})\) と長さ \(N_2\) の数列 \(Y = (Y_0, Y_1, \cdots, Y_{N_2-1})\) を用意する。 \(X_k\) は \(A_i=k\) となる \(i\) の個数、 \(Y_k\) は \(B_j=k\) となる \(j\) の個数とする。
  • これはそれぞれ \(A, B\) の頻度分布を表す。
• 長さ \(N_1+N_2-1\) の数列 \(Z=(Z_0,Z_1,\cdots, Z_{N_1+N_2-2})\) を、 \(Z_k\) を \(A_i+B_j=k\) となる \((i, j)\) の組の個数とする。
• \(Z\) は \(X\) と \(Y\) の畳み込みとして表せる。これは高速フーリエ変換で \(O((N_1+N_2) \log (N_1+N_2))\) 時間で求められる。
  • 整数列の畳み込み（素数で割った余りを求めない）は、AtCoder 上では AtCoder Library の convolution_ll を用いると便利である。