Yukicoder064 XORフィボナッチ数列

問題概要

整数列 {Fk} を次の漸化式で定義する。

$F[k]=F[k−1] ⊕ F[k−2].(k≥2)$

ただし、$⊕$ は$bitwise$ $xor$の記号である。 $F[0],F[1]$ が与えられたとき、$F[N]$ を計算せよ。

$N\leqq10^{18}$、$1\leqq F[0],F[1]\leqq10^{18}$

yukicoder064

解法

$XOR$の性質、$X ⊕ X = 1$より、$A=B⊕C $->$ A⊕C=B$である。
したがって順番に数を生成したとき、生成される数は3種類のみ。

計算量:$O(1)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using LL = long long;    using VL = vector<LL>;
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        VL F(3, 0); LL N;
        cin >> F[0] >> F[1] >> N;
        F[2] = F[1] ^ F[0];
        LL ans = F[N % 3];
        cout << ans << "\n";
    
        return 0;
    }