ARC071_D 井井井 / ###

問題

x軸に水平な直線がm本、y軸に水平な直線がn本引いてある。この中に存在している全ての長方形の面積を求める。

方針

x軸、y軸をそれぞれ別々に考える。x軸y軸それぞれについて、すべてのx[i] - x[j] (i >j)（y軸の場合(y[i]-y[j])の値を計算し、その結果をかけ合わせれば良い。 愚直にやるとまにあわない。のですべての直線の座標について、何回足して、何回引けばよいか考える。(x軸、y軸を別々に） 足す回数はx[i] - x[j] でいうところの、x[i]として計算する回数。 引く回数はx[[j]として計算する回数。 ここである座標kについて考える。 x[k]を足す回数（x[i]のところがx[k]になる回数）は k-1回、x[k]を引く回数はn-k回である。 これをy軸についても計算し、それをかければ良い。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> x(n), y(m);
    for(int i=0;i<n;i++) cin >> x[i];
    for(int i=0;i<m;i++) cin >> y[i];

    ll sum_x = 0, sum_y = 0;
    for(int i=0;i<n;i++) {
        sum_x += i * x[i] - (n-i-1) * x[i];
        sum_x %= mod;
    }
    for(int i=0;i<m;i++) {
        sum_y += i * y[i] - (m-i-1) * y[i];
        sum_y %= mod;
    }

    cout << sum_x * sum_y % mod << endl;
}