CF1208A XORinacci

URL 洛谷

题目描述

有一个”异或斐波那契数列”,让你求第$n$项,n很大。

思路

因为异或两次就可以异或回去了,所以这个数列是每三项便重复一次的。

下面给出证明:
$$f_0=a$$
$$f_1=b$$
$$f_2= a\odot b $$
$$f_3= f_2 \odot b =b$$
$$……$$
$$\therefore f_n=f_{n\mod3}$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int f[4],p,n;
int main(){
scanf("%d",&p);//多组数据
while(p--){
scanf("%d%d%d",&f[0],&f[1],&n);
f[2]=f[0]^f[1];//这样便计算第3项
printf("%d\n",f[n%3]);//只需输出第n%3项即可
}
return 0;
}