杭电第四场 hdu6336 Problem E. 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): 1384    Accepted Submission(s): 630

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

 

 

Source

2018 Multi-University Training Contest 4

 

 

Recommend

chendu   |   We have carefully selected several similar problems for you:  6373 6372 6371 6370 6369 

 

题意：给你一串数字按顺序填充矩阵，询问q次，问(x0,y0)到(x1,y1)的矩阵和

如：

3

1 10 100

是这样填充：

    1    10    1      1  10  ...

100    10  10  100  ...

100  100    1     ...

    1    10   ...

100     ...

分析：通过打表我们可以找出规律（这个得看数学直觉和平常的做题范围了）：如果是奇数大小为L*L，如果为偶数大小为2L*2L的矩阵是重复出现，所以循环节我们可以设成2L*2L

　　找到规律后我们可以先预处理求出2L*2L的矩阵前缀和，然后把要求的范围分割成多少个2L*2L的矩阵来求

AC代码：

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e3+10;
const ll mod = 1e9+7;
const double pi = acos(-1.0);
const double eps = 1e-8;
//FILE* fout = fopen("0001.out", "w");
ll n, T;
ll mapn[maxn][maxn], a[maxn];
ll dp[maxn][maxn]; //(i,j)区域的前缀和
ll get( ll s, ll t ) { //这里的s,t由x,y减一得到，有可能产生负数
    if( s == -1 || t == -1 ) { //如果s，t为负数，dp的值为0
        return 0;
    }
    ll x = s%n, cnt_x = s/n; //判断s,t范围内由几个2*n的区域组成
    ll y = t%n, cnt_y = t/n;
    //debug(x), debug(cnt_x), debug(y), debug(cnt_y);
    //debug(dp[x][n-1]), debug(dp[n-1][y]), debug(dp[x][y]);

    return dp[x][n-1]*cnt_y+dp[n-1][y]*cnt_x+dp[n-1][n-1]*cnt_x*cnt_y+dp[x][y];
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    scanf("%lld",&T);
    while( T -- ) {
        memset(dp,0,sizeof(dp));
        memset(mapn,0,sizeof(mapn));
        scanf("%lld",&n);
        for( ll i = 0; i < n; i ++ ) {
            scanf("%lld",&a[i]);
        }
        ll cur = 0;
        for( ll i = 0; i <= 100; i ++ ) {
            for( ll j = 0; j <= i; j ++ ) {
                mapn[j][i-j] = a[cur];
                cur = (cur+1)%n;
            }
        }
        dp[0][0] = mapn[0][0];
        for( ll i = 1; i < 2*n; i ++ ) {
            dp[0][i] = dp[0][i-1] + mapn[0][i];
        }
        for( ll i = 1; i < 2*n; i ++ ) {
            dp[i][0] = dp[i-1][0] + mapn[i][0];
        }
        for( ll i = 1; i < 2*n; i ++ ) {
            for( ll j = 1; j < 2*n; j ++ ) { //求前缀和
                dp[i][j] = mapn[i][j] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1];
            }
        }
        n = 2*n; //将n变成2*n 因为如果是奇数大小为L*L，如果为偶数大小为2L*2L的矩阵是重复出现
        ll q, x0, y0, x1, y1;
        scanf("%lld",&q);
        while( q -- ) {
            scanf("%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
            //fprintf( fout, "%lld\n", get(x1,y1)-get(x1,y0-1)-get(x0-1,y1)+get(x0-1,y0-1) );
            printf("%lld\n",get(x1,y1)-get(x1,y0-1)-get(x0-1,y1)+get(x0-1,y0-1));
        }
    }
    return 0;
}