Problem E. Matrix from Arrays

**Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1162 Accepted Submission(s): 522
**

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 10 100

3 3 3 3

2 3 3 3

2 3 5 8

5 1 10 10

9 99 999 1000

Sample Output

101

1068

2238

33076541

Source

2018 Multi-University Training Contest 4

解析矩阵是无限大的所以右下角没有被赋值的地方是不受影响的QAQ 长度为偶数循环矩阵是 2L*2L 所以直接按照2L算就是了二位前缀和预处理一下数一下完事了

AC代码

1#include <bits/stdc++.h>
2#define pb push_back
3#define mp make_pair
4#define fi first
5#define se second
6#define all(a) (a).begin(), (a).end()
7#define fillchar(a, x) memset(a, x, sizeof(a))
8#define huan printf("\n");
9#define debug(a,b) cout<<a<<" "<<b<<" ";
10using namespace std;
11typedef long long ll;
12const ll maxn=1e2+10,inf=0x3f3f3f3f;
13const ll mod=1e9+7;
14ll a[maxn],g[maxn][maxn],n;
15ll sum[maxn][maxn];
16void init()
17{
18    int cnt=0;
19    for(int i=0;i<4*n;++i)
20    {
21        for(int j=0;j<=i;++j) 
22        {
23            g[j][i-j]=a[cnt];
24            cnt=(cnt+1)%n;
25        }
26        
27    }
28    sum[0][0]=g[0][0];
29    for(int i=0;i<2*n;i++)
30    {
31        for(int j=0;j<2*n;j++)
32        {
33            if(i>0&&j>0)sum[i][j]=g[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
34            if(i==0&&j>0)sum[i][j]=g[i][j]+sum[i][j-1];
35            if(j==0&&i>0)sum[i][j]=g[i][j]+sum[i-1][j];
36        }
37    }
38}
39ll solve(int x,int y)
40{
41    ll ans=0;
42    ll xx=x/n;
43    ll yy=y/n;
44    ll yux=x%n;
45    ll yuy=y%n;
46    ans+=xx*yy*sum[n-1][n-1];
47    ans+=yy*sum[yux][n-1];
48    ans+=xx*sum[n-1][yuy];
49    ans+=sum[yux][yuy];
50    return ans;
51}
52int main()
53{
54    int t,q;
55    cin>>t;
56    while(t--)
57    {
58        cin>>n;
59        for(int i=0;i<n;i++)
60            cin>>a[i];
61        init();n=n*2;
62        cin>>q;
63        while(q--)
64        {
65            int x1,x2,y1,y2;
66            cin>>x1>>y1>>x2>>y2;
67            //cout<<solve(x1,y1)<<endl;
68            cout<<solve(x2,y2)-solve(x1-1,y2)-solve(x2,y1-1)+solve(x1-1,y1-1)<<endl;
69        }
70    }
71    return 0;
72}

HDU 6336 子矩阵求和

Problem E. Matrix from Arrays

评论区

相关推荐