我终于知道我有多么蠢了。。。推规律根本不带我这么推的。。。跟51nod那场比赛的傻逼B题一样，想都不想想就打表找规律。。。智障啊找规律也要按照基本法！
//f[1][2]=a[1][2] f[2][1]=a[2][1]
//f[2][2]=a[1][2]^a[2][1]
//f[2][3]=a[1][2]^a[2][1]^a[1][3]
//f[2][4]=a[1][2]^a[2][1]^a[1][3]^a[1][4]
//f[2][5]=a[1][2]^a[2][1]^a[1][3]^a[1][4]^a[1][5]
//f[3][2]=a[1][2]^a[2][1]^a[3][1]
//f[4][2]=a[1][2]^a[2][1]^a[3][1]^a[4][1]
/*
System Message (题目提供者)
a[i][j]=a[i-1][j]^a[i][j-1]=a[i-2][j]^a[i-1][j-1]^a[i-1][j-1]^a[i][j-2]=a[i-2][j]^a[i][j-2]
a[i][j]=a[i-2][j]^a[i][j-2]=a[i-4][j]^a[i-2][j-2]^a[i-2][j-2]^a[i][j-4]=a[i-4][j]^a[i][j-4]
以此类推可以发现
a[i][j]=a[i-131072][j]^a[i][j-131072]
预处理a[1..100][1..131172]与a[1..131172][1..100]
对于每个询问答案即为a[n][131072+m]^a[131072+n][m]
*/
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
const int nmax=105;
const int maxn=131173;
int f[nmax][maxn],g[maxn][nmax];
int main(){
rep(i,2,131172) {
f[1][i]=read();
if(i<=100) g[1][i]=f[1][i];
}
rep(i,2,131172){
g[i][1]=read();
if(i<=100) f[i][1]=g[i][1];
}
rep(i,2,100) rep(j,2,131172) f[i][j]=f[i][j-1]^f[i-1][j];
rep(i,2,131172) rep(j,2,100) g[i][j]=g[i][j-1]^g[i-1][j];
int t=read(),n,m;
while(t--){
n=read(),m=read();
printf("%d
",f[n][m+131072]^g[n+131072][m]);
}
return 0;
}
收藏
关注函数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犯了难，所以来找你，你能帮帮他吗？
第一行读入131171个正整数，表示i=2->131172的a[1][i](1<=a[1][i]<=1000000000)。 第二行读入131171个正整数，表示i=2->131172的a[i][1](1<=a[i][1]<=1000000000)。 第三行读入一个正整数Q(1<=Q<=10000)，表示询问的次数。 接下来Q行，每行两个数n,m(2<=n,m<=100)，表示每一组询问。
Q行，每行为f(n+131072,m+131072)
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
0 0 131072