Warning: session_start(): open(/tmp/sess_fcf4bcbab5a9b08bbf6de30dba8187b4, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/6/6a0f3843c5ea426c08feea4e44f84973.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
=====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$ 显然可以分块计算。