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): 1223    Accepted Submission(s): 548

 

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≤1e8,0≤y0≤y1≤1e8) 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

题意：根据题目中的代码，可以跑出一个无穷矩阵，然后Q次询问，每次询问给出两个点的坐标，作为子矩阵左上角和右下角的点，求子矩阵上所有数的和。

题解：打表，找规律。发现边长每2*L的矩阵是相同的。因此求出边长为2*L矩阵的前缀和。然后减一减。

#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<typeinfo>
#include<string>
#include<queue>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
using namespace std;

#define LL long long
#define scand(x) scanf("%d",&x)
#define scandd(x,y) scanf("%d%d",&x,&y)
#define scans(x) scanf("%s",x);
#define scanld(x) scanf("%lld",&x)
#define rep(i,x,n) for(int i = x;i < n;i++)
#define dep(i,x,n) for(int i = x;i > n;i--)

LL A[20];
LL M[100][100];
int main()
{
    int T;
    scand(T);
    while(T--)
    {
        int cursor = 0;
         LL L ;
        scanld(L);
        for(int i = 0;i < L;i++)
            scand(A[i]);
        for (int i = 1;i <= 4 * L ; ++i) {
            for (int j = 1; j <= i; ++j) {
                M[j][i - j + 1] = A[cursor];
                cursor = (cursor + 1) % L;
            }
        }
        rep(i,1,2 * L +1)
        {
            rep(j,1,2*L + 1)
            {
                M[i][j] = M[i][j] + M[i - 1][j]+M[i][j-1] - M[i - 1][j - 1];
            }
        }
        int q;
        scand(q);
        LL ans = 0;
        LL L2 = 2 * L;
        while(q--)
        {
            int x1,y1,x2,y2;
            scandd(x1,y1);
            scandd(x2,y2);
            x1 ++; x2 ++;y1++;y2++;
            int tx2 = (x2%L2)?(x2 % L2) : L2;
            int ty2 = (y2 % L2)?(y2%L2):L2;
            ans = M[tx2][ty2] + (y2 -1)/L2 * M[tx2][L2] + (x2-1)/L2 * M[L2][ty2] + ((x2-1) / L2)* ((y2-1) / L2) * M[L2][L2];
            int ty1 = (y1 % L2 )?(y1 % L2):(L2);
            int tx1 = (x1 % L2) ? (x1 % L2):L2;
            ans = ans - M[tx2][ty1 - 1] - (y1 - 1)/L2 * M[tx2][L2] - M[L2][ty1 - 1] * ((x2-1)/L2) - ((x2 - 1)/ L2 * ((y1 - 1)/L2) * M[L2][L2]);   //减去左边部分
            ans = ans - M[tx1 - 1][ty2] - (x1 - 1)/ L2 * M[L2][ty2] - ((y2-1)/L2) * M[tx1 - 1][L2] - (x1 - 1)/L2 * ((y2 - 1)/L2 )* M[L2][L2];  //减去上面部分
            ans = ans + M[tx1 - 1][ty1 - 1] + (y1 - 1) / L2 * M[tx1 - 1][L2] + (x1 - 1)/L2 *M[L2][ty1 - 1] +  ((x1-1) / L2)* ((y1-1) / L2) * M[L2][L2];
            cout << ans << endl;
        }
    }
}