HDU-6336 Matrix from Arrays(找循环节)

---

题目链接

---

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

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++:

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

---

题意:

给定一个矩阵生成方式，求给定子矩阵的元素之和。

思路:

显而易见的公式

$M[i][j] = A[(\frac{(i + j)(i + j + 1)}{2} + i) \mod L] = A[(\frac{3i}{2} + \frac{j}{2} + \frac{i ^ 2} {2} + \frac{j ^ 2}{2} + ij) \mod L] = M[i + 2L][j] = M[i][j + 2L]$

公式到底是怎么显而易见的呢，我们回到题目给的生成方式，M(j, i - j),其实我们可以显然的看见有一个循环，那么看到有一个是1 + 2 + 3 + 4 + …，那么内层循环了多少次呢，对于M(j, i-j)，显然是j次啊。

那么对于题目中的cursor我们可以确定每一次它的值是cursor = i × ( i + 1 ) / 2 + j;我们知道cursor是对L取模的，但是这里的cursor计算中有个除2，不能直接取模，那么我们可以将L乘以2，这样我们可以发现其实这个矩阵就是一个2L × 2L的循环矩阵，那么我们预处理前缀和，O(1)询问即可。

代码:

/*************************************************************************
    > File Name: HDU-6336.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年08月01日 星期三 19时15分56秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<string>

using namespace std;
typedef long long LL;
#define sqr(x) (x)*(x)
const double eps = 1e-8;
const double C = 0.57721566490153286060651209;
const double pi = acos(-1.0);
const LL mod = 1e9 + 7;
const int maxn = 1e5 + 10;

LL w[50][50];
int a[12], L;

LL solve(int x, int y){
    if(x < 0 || y < 0) return 0;
    return w[L-1][L-1] *(x/L) *(y/L)
    + w[L-1][y%L] * (x/L)
    + w[x%L][L-1] * (y/L)
    +w[x%L][y%L];
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &L);
        for(int i = 0; i < L; ++i)
            scanf("%d", &a[i]);
        int t = 0;
        for(int i = 0; i <= 4*L; ++i)
            for(int j = 0;j <= i; ++j)
                w[j][i-j] = a[t], t=(t+1)%L;
        L *= 2;
        for(int i = 0; i < L; ++i)
        for(int j = 0; j < L; ++j){
            if(i) w[i][j] += w[i-1][j];
            if(j) w[i][j] += w[i][j-1];
            if(i&&j) w[i][j] -= w[i-1][j-1];
        }int q;
        scanf("%d", &q);
        while(q--){
            int x0,y0,xx,yy;
            scanf("%d %d %d %d", &x0, &y0, &xx, &yy);
            printf("%lld\n", solve(xx,yy) - solve(x0-1,yy) - solve(xx,y0-1) + solve(x0-1,y0-1));
        }
    }
    return 0;
}