CF1208A XORinacci

2019-09-10 21:04:21


题目描述

有一个"异或斐波那契数列",让你求第 $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;
}