2018HDU多校赛第四场Problem E. Matrix from Arrays

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6336

Problem E. Matrix from Arrays

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

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.

题目大意：给你串整数序列，通过上述代码转换为一个数组，有q次询问，每次询问给定一个子矩阵的左上和右下两个顶点的坐标，输出这个子矩阵中所有元素之和。

思路：复制他的代码大表发现是有规律的，对于奇数，以L*L为一个循环，但为偶数时则不然，是以2L*2L为循环的，为保险起见，我们取2L为一个循环节。求出前缀和，利用容斥原理，最后用s1-s2-s3+s4即可，具体看图：

 

（0，0）到 右下端点为s4

注意：要用longlong，因为该矩阵是无限的，所以只管算就行，不会出现右下角元素全部为0的情况（上图只是示例而已）

code：

#include<bits/stdc++.h>
#define maxL 100
#define LL long long
int L ;
int M[maxL][maxL];
void print(int n)
{
    int sum = 0;
    for(int i = 0 ; i < 2*n ; i++)
    {
        for(int j = 0 ; j < 2*n ; j++)
            printf("%d " , M[i][j]);
        puts("");
    }
}
LL prefix_sum(int x , int y)
{
    LL s(0) ,s1(0) ,s2(0) ,s3(0) ,s4(0);
    int N = 2*L;
    for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j < N ; j++)
            s1 += M[i][j];
    for(int i = 0; i < x%N ; i++)
        for(int j = 0; j < N ; j++)
            s2 += M[i][j];
    s2 *= y/N;
    for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j < y%N ; j++)
            s3 += M[i][j];
    s3 *= x/N;
    for(int i = 0 ; i < x%N ; i++)
        for(int j = 0 ; j < y%N ; j++)
            s4 += M[i][j];
    //printf("%lld\n" ,s1*std::min(x/N , y/N)+s2+s3+s4);
    return s1 * (x/N) * (y/N) + s2 + s3 + s4;
}
int main()
{
    int T;
    scanf("%d" , &T);
    while(T--)
    {
        scanf("%d" , &L);
        int  A[L];
        for(int i = 0 ; i < L ; i++)
            scanf("%d" , &A[i]);
        int cursor = 0;
        for (int i = 0; i < 5*L ; ++i)
        {
            for (int j = 0; j <= i; ++j)
            {
                M[j][i - j] = A[cursor];
                cursor = (cursor + 1) % L;
            }
        }
        //print(L) ;
        int q;
        scanf("%d" , &q);
        while(q--)
        {
            int x0 ,y0 ,x1 ,y1;
            scanf("%d%d%d%d" , &x0 , &y0 , &x1 , &y1);
            printf("%lld\n" , prefix_sum(x1+1,y1+1)-prefix_sum(x1+1,y0)-prefix_sum(x0,y1+1)+prefix_sum(x0,y0));
        }
    }
    return 0;
}