問題概要

座標平面上に、 $N$ 本の直線 $x = A_{1}, A_{2}, \dots, A_{N}$ と、 $M$ 本の直線 $y = B_{1}, B_{2}, \dots, B_{M}$ がある。

これらの直線のうち 4 本を選んでできる長方形領域は ${}_{N}\mathrm{C}_{2} \times {}_{M}\mathrm{C}_{2}$ 個あるが、それらの面積の総和を 1000000007 で割った余りを求めよ。

制約

$2 \le N, M \le 10^{5}$

考えたこと

実は、x 軸方向と y 軸方向とは独立に考えることができる！

具体的には、

「 $A_{1}, \dots, A_{N}$ から 2 個を選んだ差」の総和を $X$
「 $B_{1}, \dots, B_{N}$ から 2 個を選んだ差」の総和を $Y$

とすると、答えは $XY$ となる。

主客転倒

よって、「 $A_{1}, \dots, A_{N}$ から 2 個を選んだ差」の総和を求める問題へと帰着された。これを求めるために、次の方針を立てることにした。

区間 $\lbrack A_{1}, A_{2})$ が被覆される回数 ( $\times$ 区間長)
区間 $\lbrack A_{2}, A_{3})$ が被覆される回数 ( $\times$ 区間長)
$\dots$
区間 $\lbrack A_{N-1}, A_{N})$ が被覆される回数 ( $\times$ 区間長)

をそれぞれ求めて、総和をとる。

たとえば、 $N = 8$ として、区間 $\lbrack A_{4}, A_{5})$ が被覆される回数を考えよう。これは下図のように、

$A_{4}$ も含めて、その左側にある点の個数
$A_{5}$ も含めて、その右側にある点の個数

を求めて、その積をとればよい。

この方針を一般化して記述すると AC となる。計算量は $O(N + M)$ である。

コード

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

int main() {
    long long N, M;
    cin >> N >> M;
    vector<long long> X(N), Y(M);
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int i = 0; i < M; i++) cin >> Y[i];

    long long xsum = 0, ysum = 0;
    for (long long i = 0; i+1 < N; i++) {
        long long num = (N*(N-1)/2 - i*(i+1)/2 - (N-i-2)*(N-i-1)/2) % MOD;
        xsum += (X[i+1] - X[i]) % MOD * num % MOD;
        xsum %= MOD;
    }
    for (long long i = 0; i+1 < M; i++) {
        long long num = (M*(M-1)/2 - i*(i+1)/2 - (M-i-2)*(M-i-1)/2) % MOD;
        ysum += (Y[i+1] - Y[i]) % MOD * num % MOD;
        ysum %= MOD;
    }
    cout << xsum * ysum % MOD << endl;
}