ABC058

[ABC058D] 井井井

题面翻译

给定 \(n\) 条平行于 \(y\) 轴的直线 \(x_{1...n}\)，和 \(m\) 条平行于 \(x\) 轴的直线 \(y_{1...n}\)，

计算 \(x_i,x_j\) 和 \(y_k,y_l\) 组成的矩形面积之和，\(1\le x<y\le n\)，\(1\le k<l\le m\)。

题目描述

$ 2 $ 次元平面上に $ x $ 軸と平行な直線が $ m $ 本と $ y $ 軸と平行な直線が $ n $ 本引いてあります。 $ x $ 軸と平行な直線のうち下から $ i $ 番目は $ y = y_i $ で表せます。 $ y $ 軸と平行な直線のうち左から $ i $ 番目は $ x = x_i $ で表せます。

この中に存在しているすべての長方形についてその面積を求め、 合計を $ 10^9+7 $ で割ったあまりを出力してください。

つまり、$ 1 i < j n $ と $ 1 k < l m $ を満たすすべての組 $ (i,j,k,l) $ について、 直線 $ x=x_i $, $ x=x_j $, $ y=y_k $, $ y=y_l $ で囲まれる 長方形の面積を求め、合計を $ 10^9+7 $ で割ったあまりを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ n $ $ m $ $ x_1 $ $ x_2 $ $ ... $ $ x_n $ $ y_1 $ $ y_2 $ $ ... $ $ y_m $

输出格式

長方形の面積の合計を $ 10^9+7 $ で割ったあまりを $ 1 $ 行に出力せよ。

样例 #1

样例输入 #1

3 3
1 3 4
1 3 6

样例输出 #1

60

样例 #2

样例输入 #2

6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677

样例输出 #2

835067060

提示

制約

• $ 2  n,m  10^5 $
• $ -10^{9  x_1 < ... < x_n  10}9 $
• $ -10^{9  y_1 < ... < y_m  10}9 $
• $ x_i, y_i $ は整数である。

Sample Explanation 1

この入力を図にすると、以下のようになります。  長方形 A,B,...,I それぞれの面積を合計すると $ 60 $ になります。 

思路

一开始想的是枚举可能有多少种排列方式（构成整个大矩形），然后统计输出即可，但是好像不合题意？

思路参考自：[【题解】AT2394 ARC071B] 井井井 / ### - 洛谷专栏 (luogu.com.cn)

可以将线段分解成相邻两直线之间的距离，如\(x_i-x_{i-1}\)，那么只需要枚举左右端点：\((i-1)*(n-i+1)\)。

就可以得到所有的情况\((x_i-x_{i-1})*(i-1)*(n-i+1)\)。同理\(y\)也是如此。最后\(sumx*sumy\)即为答案，注意不要忘记取模。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+10;
const ll mod=1e9+7;
const ll INF=1e11;
ll x[MAXN],y[MAXN];
ll qpower(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1)ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    ll n,m;cin>>n>>m;
    ll sumx=0,sumy=0;
    for(int i=1;i<=n;i++)cin>>x[i];
    for(int i=1;i<=m;i++)cin>>y[i];
    for(int i=2;i<=n;i++)sumx=(sumx+(x[i]-x[i-1])*(i-1)*(n-i+1))%mod;
    for(int i=2;i<=m;i++)sumy=(sumy+(y[i]-y[i-1])*(i-1)*(m-i+1))%mod;
    ll ans=0;
    ans=(sumx*sumy)%mod;
    cout<<ans;
    return 0;
}