HDU 6336 Matrix from Arrays（找规律）

Problem E. Matrix from Arrays

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 884    Accepted Submission(s): 396
 

Problem Description

Kazari has an array A length of L, she plans to generate an infinite matrix M using A.
The procedure is given below in C/C++:

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;
    }
}

Her friends don't believe that she has the ability to generate such a huge matrix, so they come up with a lot of queries about M, each of which focus the sum over some sub matrix. Kazari hates to spend time on these boring queries. She asks you, an excellent coder, to help her solve these queries.

Input

The first line of the input contains an integer T (1≤T≤100) denoting the number of test cases.
Each test case starts with an integer L (1≤L≤10) denoting the length of A.
The second line contains L integers A0,A1,...,AL−1 (1≤Ai≤100).
The third line contains an integer Q (1≤Q≤100) denoting the number of queries.
Each of next Q lines consists of four integers x0,y0,x1,y1 (0≤x0≤x1≤108,0≤y0≤y1≤108) querying the sum over the sub matrix whose upper-leftmost cell is (x0,y0) and lower-rightest cell is (x1,y1).

Output

For each test case, print an integer representing the sum over the specific sub matrix for each query.

Sample Input

1		
3		
1 10 100
5		
3 3 3 3
2 3 3 3
2 3 5 8
5 1 10 10
9 99 999 1000

Sample Output

1
101
1068
2238
33076541

题目大意：给你一个矩阵生成的代码，求生成的矩阵的子矩阵的和

打表可以发现规律，就是当数组长度是偶数时，矩阵以奇数循环，比如样例，大矩阵是由3*3的小矩阵组成的（可以自己打表看看），如果数组长度是偶数，那么矩阵以偶数的两倍循环，比如长度是4，大矩阵是由8*8的小矩阵生成。

得到这样的规律，我们就可以解决这个题了，比如我们要求2 3 5 8的子矩阵的和，我们先预处理好循环矩阵的二维前缀和，那么2 3 5 8可以等于sum[5][8]-sum[5][2]-sum[1][8]+sum[1][2]（多减的部分要加回来），然后再把这些映射到循环矩阵中，比如求sum[x][y]，先求出它包含多少个循环矩阵，然后是那些行多出来一点，列多出来一点的小矩阵，最后是占着别的矩阵的一角的小矩阵

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=110;
ll n;
ll num[maxn];
ll map[maxn][maxn];
ll sum[maxn][maxn];
ll cal(ll x,ll y)
{
	ll a=x/n;
	ll b=y/n;
	x=x%n;
	y=y%n;
	return a*b*sum[n-1][n-1]+a*sum[n-1][y]+b*sum[x][n-1]+sum[x][y];
}
int main()
{
	int test;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%lld",&n);
		for(ll i=0;i<n;i++)
		{
			scanf("%lld",&num[i]);
		}
		int cursor = 0;
		for (int i = 0;i<110 ; ++i) {
			for (int j = 0; j <= i; ++j) {
				map[j][i - j] = num[cursor];
				cursor = (cursor + 1) % n;
			}
		}
		if(n%2==0) n*=2;
		sum[0][0]=map[0][0];
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(i==0&&j==0)
				{
					sum[i][j]=map[i][j];
				}
				if(i==0)
				{
					sum[i][j]=sum[i][j-1]+map[i][j];
				}
				else if(j==0)
				{
					sum[i][j]=sum[i-1][j]+map[i][j];
				}
				else
				{
					sum[i][j]=sum[i-1][j]+sum[i][j-1]+map[i][j]-sum[i-1][j-1];
				}
			}
		}
		int q;
		scanf("%d",&q);
		while(q--)
		{
			ll x0,y0,x1,y1;
			scanf("%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
			printf("%lld\n",cal(x1,y1)-cal(x1,y0-1)-cal(x0-1,y1)+cal(x0-1,y0-1));
		}
	}
	return 0;
}