Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 419 Accepted Submission(s): 180
for (int i = 0; ; ++i) {
for (int j = 0; j <= i; ++j) {
M[j][i - j] = A[cursor];
cursor = (cursor + 1) % L;
}
}
比赛的时候其实知道做法了，打表后可以发现这个矩阵的行列都是由循环节的而且行列的循环长度一致，
只不过一开始默认为是L，后来发现奇数是L，偶数是2*L,我们都按照2*L来做就好了，预处理出来行和列的
前缀和然后容斥的处理询问。
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define pii pair<int,int> #define mp make_pair #define LL long long int cursor = 0; int M[115][115],A[15],L,len; LL pre1[25][25],pre2[25][25]; LL g[25]; LL sum(int x,int y){ if(x<=0||y<=0) return 0; LL ans=0; for(int i=1;i<=len;++i){ g[i]=g[i-1]+pre1[i][len]*(y/len)+pre1[i][y%len]; } return g[len]*(x/len)+g[x%len]; } int main(){ int t,n,m,i,j,k,Q; int x1,y1,x2,y2; cin>>t; while(t--){ scanf("%d",&L); len=L*2; memset(pre1,0,sizeof(pre1)); memset(pre2,0,sizeof(pre2)); for(i=0;i<L;++i) scanf("%d",A+i); int cursor = 0; for (int i = 0;i<=100; ++i) { for (int j = 0; j <= i; ++j) { M[j+1][i - j+1] = A[cursor]; cursor = (cursor + 1) % L; } } for(i=1;i<=len;++i){ for(j=1;j<=len;++j){ pre1[i][j]=M[i][j]+pre1[i][j-1]; pre2[i][j]=M[j][i]+pre2[i][j-1]; } } scanf("%d",&Q); while(Q--){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++,y1++,x2++,y2++; printf("%lld\n",sum(x1-1,y1-1)+sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)); } } return 0; }
原文：https://www.cnblogs.com/zzqc/p/9404488.html