[ 2018 Multi-University Training Contest 4 ] [ HDU6336 ] E Matrix from Arrays

        题目大意：给出一个长度为L的数组\(A[0..L-1]\)，用下面的方法来构造出一个无限大的矩阵：

int cursor = 0;
for (int i = 0; ; ++i) {
    for (int j = 0; j <= i; ++j) { 
        M[j][i - j] = A[cursor];
        cursor = (cursor + 1) % L;
    }
}

        给出Q个询问\( ( Q \leq 100 ) \)，求左上角为\(x_0,y_0\)，右下角为\(x_1,y_1\)的子矩阵内的元素和。\( 1 \leq L \leq 10 , 0 \leq x_0 , y_0 , x_1 , y_1 \leq 10^8 \)。

        题解：首先可以先把\(M[i][j]\)的表达式写出来：\(M[i][j] = A[ (C_{i+j+1}^2 + i) % L]\)，利用该式可以得到\(M[i][j] = M[i+2L][j] = M[i][j+2L]\)，然后就可以很轻松地解决掉此题了。

        考场上没有发现这个性质，只是知道会存在循环节，且循环节长度不大于\(L^2\)，利用这个性质来进行计算。另外由于最多只有L个不同的数，可以统计出每个数出现的次数再计算。

        对于图中的任意一个子矩阵，可以由四个以\( (0,0) \)为左上角顶点的矩阵容斥得到。然后要计算的是以\( (0,0) \)为左上角的矩阵内元素和，这个再容斥求。

        矩阵可以用两个直角梯形减去一个大三角形，直角梯形可以用以左上角为\( (0,0) \)的等腰直角三角形与一个平行四边形相加而成，平行四边形的底上的数字是有周期的，然后高又是固定的，可以在\( O(L^2) \)的时间内预处理出来。

        所以浪费了很多时间来搞这个东西...脑子都搞糊了...

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

long long C2(int X) {return (long long)X*(X-1)/2;}

long long c[maxn];
int A[maxn];
int L,Q;

void Calc_Triangle(int X,int sgn)
{
	for (int i=0;i<L;i++) c[i]+=((C2(X)+L-i-1)/L)*sgn;
}

long long POS(int X,int Y) {return C2(X+Y+1)+X;}
int POSL(int X,int Y) {return POS(X,Y)%L;}

void Calc_Rectangle(int X0,int Y0,int DX,int DY,int Len,int Time)
{
	int c0[maxn];
	int c1[maxn][maxn];
	int vis[maxn][maxn];
	memset(c0,0,sizeof(c0));
	memset(c1,0,sizeof(c1));
	memset(vis,0,sizeof(vis));
	for (int i=0;i<L;i++)
	for (int j=0;j<L;j++)
		c1[i][j]=(Len+j+L-i-1)/L-(i<j?1:0);
	int cnt=0;
	while (1)
	{
		int PA=POSL(X0,Y0),PB=POSL(X0+DX,Y0+DY);
		if (vis[PA][PB]) break;
		vis[PA][PB]=++cnt;
		for (int i=0;i<L;i++) c0[i]+=c1[i][PA];
		X0+=DX,Y0+=DY;
	}
	long long K=Time/cnt;
	Time%=cnt;
	for (int i=0;i<L;i++) c[i]+=c0[i]*K;
	while (Time--)
	{
		int P=POSL(X0,Y0);
		for (int i=0;i<L;i++) c[i]+=c1[i][P];
		X0+=DX,Y0+=DY;
	}
	return;
}

long long Query(int X,int Y)
{
	if (X==-1 || Y==-1) return 0;
	memset(c,0,sizeof(c));
	Calc_Triangle(X+2,1);
	Calc_Triangle(Y+2,1);
	Calc_Triangle(X+Y+2,-1);

	Calc_Rectangle(0,X+1,0,1,X+1,Y);
	Calc_Rectangle(1,Y,1,0,Y+1,X);

	long long res=0;
	for (int i=0;i<L;i++) res+=c[i]*A[i];
	return res;
}

int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&L);
		for (int i=0;i<L;i++) scanf("%d",&A[i]);
		scanf("%d",&Q);
		while (Q--)
		{
			int X0,Y0,X1,Y1;
			scanf("%d%d%d%d",&X0,&Y0,&X1,&Y1);
			printf("%lld\n",Query(X1,Y1)-Query(X0-1,Y1)-Query(X1,Y0-1)+Query(X0-1,Y0-1));
		}
	}
	return 0;
}