数学

利用矩阵加速法计算\(Fibbonaci_n\)

\[ \begin{bmatrix} Fib_n \\ Fib_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} Fib_{n-1} \\ Fib_{n-2} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} Fib_1 \\ Fib_0 \end{bmatrix} \]

计算\(\displaystyle \begin{bmatrix} 1& 1\\ 1&0 \end{bmatrix}^{n-1}\)时，采用类似快速幂的进制拆法。

【异或性质】对序列\(A=\left \{ a_1,a_2,\cdots,a_n\right \},n为奇数\)，内部的数两两相同的可以配为一对，找出落单的数，求其值。

将此序列求异或和即可。