欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 6336 Matrix from Arrays(循环节)

程序员文章站 2022-07-12 09:31:18
...

题目链接:Matrix from Arrays

题意

给定一个长度为 L 的数组 A0,A1AL1,用以下代码生成一个无穷大矩阵:

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 次询问,每次询问为从第 x0y0 列到第 x1y1 列的子矩阵中数字的和。

输入

第一行为一个整数 T (1T100),接下有 T 组数据,每组数据第一行为一个整数 L (1L10),第二行为 L 个整数 A0,A1,AL1 (1Ai100),第三行为一个整数 Q (1Q100),接下去 Q 行每行四个整数 x0,y0,x1,y1 (0x0x1108,0y0y1108)

输出

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

样例

输入
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 的矩阵,就可以通过循环节求出所有矩阵的值,设 Sx,y 为无穷大矩阵前 xy 列的和,则所求子矩阵的和为

Sx1,y1Sx01,y1Sx1,y01+Sx01,y01
注意 x0,y0 取得 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;
}