yukicoder No.64 XORフィボナッチ数列 解説

問題文

解説

まず、$F$の要素を一つずつ調べてみる。
すると、計算量は$O(N)$なので、余裕でTLEする。
ここで、$F_0=A,F_1=B,A \oplus B=C$とする。
$A \oplus B=C,A \oplus C=B,B \oplus C=A$なので、実は$F$は次のように並ぶ。
$A,B,C,A,B,C,A...$こんな感じに。
よって$N mod 3$の数によって判定すればよい。
$F_0,F_1$が$10^{18}$と十分に大きいので注意。

C++での解答例

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
  ll F_0,F_1,N;cin>>F_0>>F_1>>N;
  if(N%3==0)cout<<F_0<<endl;
  if(N%3==1)cout<<F_1<<endl;
  if(N%3==2)cout<<(F_0^F_1)<<endl;
}