HDU 6336 Matrix from Arrays（循环节）

题目链接：Matrix from Arrays

题意

给定一个长度为 L$L$ 的数组 A0,A1⋯AL−1$A_0,A_1\cdots A_{L-1}$，用以下代码生成一个无穷大矩阵：

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

有 Q$Q$ 次询问，每次询问为从第 x0$x_0$ 行 y0$y_0$ 列到第 x1$x_1$ 行 y1$y_1$ 列的子矩阵中数字的和。

输入

第一行为一个整数 T (1≤T≤100)$T(1\le T\le 100)$，接下有 T$T$ 组数据，每组数据第一行为一个整数 L (1≤L≤10)$L(1\le L\le 10)$，第二行为 L$L$ 个整数 A0,A1⋯,AL−1 (1≤Ai≤100)$A_0,A_1\cdots ,A_{L-1}(1\le A_i\le 100)$，第三行为一个整数 Q (1≤Q≤100)$Q(1\le Q\le 100)$，接下去 Q$Q$ 行每行四个整数 x0,y0,x1,y1 (0≤x0≤x1≤108,0≤y0≤y1≤108)$x_0,y_0,x_1,y_1(0\le x_0\le x_1\le {10}^8,0\le y_0\le y_1\le {10}^8)$。

输出

对于每次询问，输出结果。

样例

输入

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

输出

1
101
1068
2238
33076541

题解

打表可以发现矩阵的循环节为 2L$2L$，因此可以只打出 2L×2L$2L\times 2L$ 的矩阵，就可以通过循环节求出所有矩阵的值，设 Sx,y$S_{x,y}$ 为无穷大矩阵前 x$x$ 行 y$y$ 列的和，则所求子矩阵的和为

Sx1,y1−Sx0−1,y1−Sx1,y0−1+Sx0−1,y0−1$$S_{x_1,y_1}-S_{x_0-1,y_1}-S_{x_1,y_0-1}+S_{x_0-1,y_0-1}$$

注意 x0,y0$x_0,y_0$ 取得 0$0$ 的情况。

过题代码

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

#define LL long long
const int maxn = 100 + 100;
int T, n, q;
int a[maxn];
LL num[maxn][maxn];

LL Sum(int x, int y) {
    if(x < 0 || y < 0) {
        return 0;
    }
    int nn = n << 1;
    LL ret = num[nn - 1][nn - 1] * ((x + 1) / nn) * ((y + 1) / nn);
    int xx = x % nn;
    int yy = y % nn;
    if(xx != nn - 1) {
        ret += num[xx][nn - 1] * ((y + 1) / nn);
    }
    if(yy != nn - 1) {
        ret += num[nn - 1][yy] * ((x + 1) / nn);
    }
    if(xx != nn - 1 && yy != nn - 1) {
        ret += num[xx][yy];
    }
    return ret;
}

int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);

    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        int Index = 0;
        for(int i = 0; i < maxn; ++i) {
            for(int j = 0; j <= i; ++j) {
                num[j][i - j] = a[Index];
                Index = (Index + 1) % n;
            }
        }
        for(int i = 0; i < maxn; ++i) {
            for(int j = 0; j < maxn; ++j) {
                if(i != 0) {
                    num[i][j] += num[i - 1][j];
                }
                if(j != 0) {
                    num[i][j] += num[i][j - 1];
                }
                if(i != 0 && j != 0) {
                    num[i][j] -= num[i - 1][j - 1];
                }
            }
        }
        scanf("%d", &q);
        int x1, x2, y1, y2;
        while(q--) {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            LL ans = Sum(x2, y2) + Sum(x1 - 1, y1 - 1);
            ans -= Sum(x2, y1 - 1) + Sum(x1 - 1, y2);
            printf("%I64d\n",  ans);
        }
    }

    return 0;
}