学习犹如逆水行舟，不进则退

UPC-###

题目描述

On a two-dimensional plane, there are m lines drawn parallel to the x axis, and n lines drawn parallel to the y axis. Among the lines parallel to the x axis, the i-th from the bottom is represented by y=y_i. Similarly, among the lines parallel to the y axis, the i-th from the left is represented by x=x_i.
For every rectangle that is formed by these lines, find its area, and print the total area modulo 10⁹+7.
That is, for every quadruple (i,j,k,l) satisfying 1≤i<j≤n and 1≤k<l≤m, find the area of the rectangle formed by the lines x=x_i, x=x_j, y=y_k and y=y_l, and print the sum of these areas modulo 10⁹+7.
Constraints
2≤n,m≤10⁵
−10⁹≤x₁<…<x_n≤10⁹
−10⁹≤y₁<…<y_m≤10⁹
x_i and y_i are integers.

翻译

在一个二维的平面上，被画上了m条平行于x轴的平行线，与n条平行于y轴的平行线。在平行于x轴的直线中，从底部向上第i个平行于x的直线由y_i来表示，同样，从左边向右第i个平行于x的直线由x_i来表示。
对于每一个由这些直线围城的矩形，求出他们的面积，并且输出所有的对10⁹+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⁹+7取余。
限制条件
−10⁹≤x₁<…<x_n≤10⁹
−10⁹≤y₁<…<y_m≤10⁹
x_i 和 y_i 都是整数

输入

Input is given from Standard Input in the following format:
n m
x₁ x₂ … x_n
y₁ y₂ … y_m

翻译

输入来自标准输入，格式如下:
n m
x₁ x₂ … x_n
y₁ y₂ … y_m

输出

Print the total area of the rectangles, modulo 10⁹+7.

翻译

输出对10⁹+7取模后的所有面积。

Sample Input

3 3
1 3 4
1 3 6

Sample Output

60

Hint

下图说明了这个输入:

下面是9个矩形的总面积A, B，…，如下图所示，为60。下图说明了这个输入:

思路解析

总结一下就是一个公式
$\sum_{1≤a<b≤4}\sum_{1≤c<d≤4}\left ( b-a \right )\left ( d-c \right )\,$1≤a<b≤4∑​1≤c<d≤4∑​(b−a)(d−c)
如果还是不明白怎么一回事，接下的动态图足以说明一切

然后就用美味可口的数学芝士把公式拆开就可以得到
$\sum_{1≤a<b≤4}\left ( b-a \right )*\sum_{1≤c<d≤4}\left ( d-c \right )\,$1≤a<b≤4∑​(b−a)∗1≤c<d≤4∑​(d−c)

之后就根据这个公式求除所有的面积
但是这是有规律的，画一下图寻找一下

OK，附上代码
AC时间到！！

#include<iostream>
#include<algorithm>
#include<string.h>
#include<map>
#include<string>
#include<math.h>
#include<stdio.h>
#pragma GCC optimize(2)
#define Swap(a,b)  a ^= b ^= a ^= b
using namespace std;
typedef long long ll;
const int MAXN=10010;
const ll long_inf=9223372036854775807;
const int int_inf=2147483647;
inline ll read() {
	ll c=getchar(),Nig=1,x=0;
	while(!isdigit(c)&&c!='-')c=getchar();
	if(c=='-')Nig=-1,c=getchar();
	while(isdigit(c))x=((x<<1)+(x<<3))+(c^'0'),c=getchar();
	return Nig*x;
}
ll N=1e9+7;
ll x[100005],y[100005];
int main() {
	ll a,b;
	cin>>a>>b;
	for(ll i=0; i<a; i++)
		x[i]=read();
	for(ll j=0; j<b; j++)
		y[j]=read();
	ll sumx=0,sumy=0;
	for(ll i=1; i<a; i++) {
		sumx+=(((((a-i)%N)*i)%N)*((x[i]-x[i-1])%N));
		sumx%=N;
	}
	for(ll i=1; i<b; i++) {
		sumy+=(((((b-i)%N)*i)%N)*((y[i]-y[i-1])%N));
		sumy%=N;
	}
	cout<<(sumx*sumy)%N<<endl;
}

如果不算(n-i)*i而是跑遍所有的话一定会超时，所以这个地方起到优化的作用，避免重复计算.

书山有路勤为径，学海无涯苦作舟。

By-轮月