题意： 给出矩阵M，求M*M矩阵的r行c列的数，每个查询跟前一个查询的结果有关。
解法： 观察该矩阵得知，令ans = M*M，则 ans[x][y] = (n-1-x行的每个值)*(n-1+y列的每个值)。直接对每个查询做n次累加(n*m=10^8的复杂度)竟然可以水过。
官方题解给的是n^2的算法，维护一个前缀和，即sum[i][j] 表示 i+j不变的所有sum[i][j]之和。
因为
ans[x][y]就是 a[y]*a[2*n-x] + .... + a[y+n-1]*a[n-x+1]，乘的这部分a[i]*a[j]，i+j是定值，求一个前缀和后O(1)求ans[x][y]，
ans[x][y] = sum[2*n-x-2][y]-sum[n-2-x][n+y]; 这点我还不太理解。
先贴O(n*m)的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define lll __int64
using namespace std;
#define N 100007 int t[]; int main()
{
int n,m,i,j;
int x,y,ans;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<=*n-;i++)
scanf("%d",&t[i]);
scanf("%d",&m);
lll sum = ;
ans = ;
for(i=;i<m;i++)
{
scanf("%d%d",&x,&y);
x = (x+ans)%n;
y = (y+ans)%n;
ans = ;
for(j=;j<n;j++)
ans += t[n--x+j]*t[n-+y-j];
sum += ans;
}
cout<<sum<<endl;
}
return ;
}
再附上meetzyc的官方做法代码：
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <string>
#include <math.h>
using namespace std;
int x,y,i,j,n,m,a[],e[][]; int main()
{
while(scanf("%d",&n)!=EOF)
{
for(i=;i<*n-;i++)
scanf("%d",&a[i]);
memset(e,,sizeof(e));
for(i=;i<=*n-;i++)
{
e[i][*n-]=a[i]*a[*n-];
for(j=*n-;j>=;j--)
e[i][j]=e[i-][j+]+a[i]*a[j];
}
scanf("%d",&m);
__int64 sum=;
int ans=;
for(i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
x = (x+ans)%n;
y = (y+ans)%n;
ans = e[*n-x-][y]-e[n--x][n+y];
sum += ans;
}
printf("%I64d\n",sum);
}
return ;
}