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}$$

代码

#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;
}