[筆記] Codeforces 1208A: XORinacci

[題意] 其實就是算 Fibonacci number，只是原本是 $F(n) = F(n-1) + F(n-2)$ 變成了 $F(n) = F(n-1) ⊕ F(n-2)$，其中 ⊕ 是 bitwise xor 運算，並且 F(0)及 F(1) 是題目給定而不是定值。

這題本來想都沒想就直接用暴力解嘗試看看，結果最後超時，後來才發現他一組測資中會有 1000 個 F(n) 要算，而 n 最大是 $10^9$，一定超時，所以才乖乖推算數字規律。

不過這規律其實很好推算，看前 6 組數字就好：
$$F(0) = a$$$$F(1) = b$$$$F(2) = a ⊕ b$$$$F(3) = (a ⊕ b) ⊕ (b) = a$$$$F(4) = a ⊕ (a ⊕ b) = b$$$$F(5) = b ⊕ a$$

結論：$F(n) = F(n\ mod\ 3)$