hdu 6336 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): 1286 Accepted Submission(s): 583
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.
思路:
M[i][j]=A[((i+j)*(i+j+1))%L]。
进一步推得M[i][j]=M[i+2*L][j]+M[i][j+2*L]。
代码:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=33;
ll a[maxn][maxn],A[maxn],sum[maxn],r[maxn];
int L;
ll query(int x0,int y0,int x1,int y1)
{
ll ans=0;
for(int i=0;i<L;i++) sum[i]=(y1-y0+1)/L*r[i];
y1-=(y1-y0+1)/L*L;
for(int i=0;i<L;i++)
{
for(int j=y0;j<=y1;j++) sum[i]+=a[i][j%L];
ans+=sum[i];
}
ans=(x1-x0+1)/L*ans;
x1-=(x1-x0+1)/L*L;
for(int i=x0;i<=x1;i++) ans+=sum[i%L];
return ans;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%d",&L);
for(int i=0;i<L;i++) scanf("%lld",&A[i]);
for(int i=0;i<2*L;i++)
for(int j=0;j<2*L;j++)
a[i][j]=A[((i+j)*(i+j+1)/2+i)%L];
L*=2;
memset(r,0,sizeof(r));
for(int i=0;i<L;i++)
{
for(int j=0;j<L;j++) r[i]+=a[i][j];
}
int Q;scanf("%d",&Q);
while(Q--)
{
int x0,x1,y0,y1;
scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
printf("%lld\n",query(x0,y0,x1,y1));
}
}
return 0;
}
推荐阅读
-
【hdu 6336】 Matrix from Arrays
-
HDU 6336 Matrix from Arrays(循环节)
-
hdu 6336 Matrix from Arrays
-
HDU 6336 Problem E. Matrix from Arrays(找规律)
-
hdu6336 多校第四场E题 Matrix from Arrays
-
HDU 6336 Matrix from Arrays(找规律)
-
hdu 6336 Problem E. Matrix from Arrays
-
杭电第四场 hdu6336 Problem E. Matrix from Arrays 打表找规律 矩阵前缀和(模板)
-
HDU6336 Problem E. Matrix from Arrays
-
杭电多校04补题 HDU6336 Problem E. Matrix from Arrays【构造】