灵台县门户网站/新浪疫情实时数据

函数f(n,m)
{
若n=1或m=1返回a[n][m];
返回f(n-1,m)异或f(n,m-1);
}
读入2<=n,m<=100
for i=2->100读入a[1][i]
for i=2->100读入a[i][1]
输出f(n,m)

发现当n,m较大时程序变得异常缓慢。
小b经过一番思考，很快解决了这个问题。
这时小c出现了，我将n,m都增加131072，你还能解决吗？
相对的，我会读入2->131172的所有a[1][i]和a[i][1]。
小b犯了难，所以来找你，你能帮帮他吗？
Input
第一行读入131171个正整数，表示i=2->131172的a[1]i。
第二行读入131171个正整数，表示i=2->131172的a[i]1。
第三行读入一个正整数Q(1<=Q<=10000)，表示询问的次数。
接下来Q行，每行两个数n,m(2<=n,m<=100)，表示每一组询问。
Output
Q行，每行为f(n+131072,m+131072)
Input示例
2 3 4 5 6 7 8 … 131171 131172
2 3 4 5 6 7 8 … 131171 131172
3
2 2
2 3
2 4
Output示例
0
0
131072

题解
f[i][j]=f[i-x][j]^f[i][j-x]
-> f[n+131072][m+131072]=f[n][m+131072]^f[n+131072][m]
所以预处理两个矩阵a1[100][131172],a2[131172][100]

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#define mod 1000000007
#define ll long long 
#define N 10000005 
#define inf 0x7fffffff
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int a[105][131371],b[131371][105];
void build()
{for (int i=2;i<=100;i++) a[i][1]=b[i][1],b[1][i]=a[1][i];for (int i=2;i<=100;i++)for (int j=2;j<=131172;j++){a[i][j]=a[i-1][j]^a[i][j-1];b[j][i]=b[j-1][i]^b[j][i-1];}
}
int main()
{for (int i=2;i<=131172;i++) a[1][i]=read();for (int i=2;i<=131172;i++) b[i][1]=read();build();int Case=read();while (Case--){int n=read(),m=read();printf("%d\n",a[n][m+131072]^b[n+131072][m]);}return 0;
}