CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

=====fib数列=====
题意：$f(x+1)=f(x)+f(x-1)+(-1)^n+x\%5+\lfloor{\log_{2}{x}}\rfloor,f(1)=f(2)=1$ ，求第 $n$ 项。 $n\le10^{18}$ \\
题解：构造两个矩阵$$A=\left(\begin{array} {} 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 2 & 3 & 4 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 {} \end{array}\right) , F=\left(\begin{array} {} f(x) \\ f(x-1) \\ (-1)^{n} \\ s \\ ? \\ ? \\ ? \\ ? \\ ? \end{array}\right) $$ 其中 $?$ 代表着 $0,1$ ，起始状态 $$F=\left(\begin{array} {} 1 \\ 1 \\ 1 \\ 2 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{array}\right) $$ 这样通过矩阵快速幂就可以很好地解决除了 $\log$ 之外的项了。而对于 $\lfloor{\log_{2}{x}}\rfloor$ 显然可以分块计算。

CVBB ACM Team

用户工具

站点工具

页面工具