斐波那契與異或

/ 0评 / 0

记一个看不出矩阵瞎搞的过程

备忘:

由高斯消元得递推式$ f(x)=f(x-1)+5f(x-2)+f(x-3)-f(x-4)$得矩阵快速幂

$ \begin{bmatrix} 1 & 5 & 1 & -1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \end{bmatrix} *\begin{bmatrix} f(x-1) \\ f(x-2) \\ f(x-3) \\ f(x-4) \end{bmatrix}=\begin{bmatrix} f(x) \\ f(x-1) \\ f(x-2) \\ f(x-3) \end{bmatrix}$

$ A^{n-4}* \begin{bmatrix} f(4)=36 \\ f(3)=11 \\ f(2)=5 \\ f(1)=1 \end{bmatrix}= \begin{bmatrix} f(x) \\ f(x-1) \\ f(x-2) \\ f(x-3) \end{bmatrix}$

$ f(x)=A[0][1] * f(4)+f[0][1] * f(3)+f[0][2] * f(2)+f[0][3] * f(4)$

异或+矩阵快速幂(excel+python打表法)

$ f(x)=f(x-1)+f(x-2) \ , (f(0)=0,f(1)=f(2)=1)$

如果$ n$为奇数$ f(n)=(f(n-1)+f(n-2)) \ xor \ 1$

$ if(c=a+b为奇数) \ c \ xor \ 1=c-1;$

$ else \ c=c+1$

如果$ n$为偶数$ f(n)=(f(n-1)+f(n-2)) \ xor \ 0$

打表可轻松得

$ w(x)=\frac{ Fi(x)-g(x)}{2}=a_x-a_{x-1}$

$ g(x)=0 \ ,if(n是6的倍数)$

$ g(x)=-1,if(n-1是6的倍数)$

$ g(x)=-2,if(n是3的倍数且\frac{n}{3}为奇数)$

$ g(x)=1,if(其余情况)$

$\displaystyle \sum_{i=1}^{k} g(x) = (-k+(\frac{k}{6}+(\frac{k-1}{6}+1) \times 2+\frac{ k/3+1 } {2} *3)$

$ \displaystyle a_n=(\sum_{i=2}^{n}w(i) \ ) +1$

$ \displaystyle \sum_{i=2}^{n}w(i)=(\sum_{i=1}^{n}w(i) )\ -1$

$ \displaystyle a_n=\sum_{i=1}^{n}w(i)=\frac{\sum_{i=1}^{n}Fi(i) \ -\sum_{i=1}^{n}g(i)}{2}=\frac{Fi(n+2)-1-\sum_{i=1}^{n}g(i)}{2}

python 打表代码

顺便改写$Java$ 对付下$ n=10^{100}

发表评论

电子邮件地址不会被公开。 必填项已用*标注