2020-2021:teams:farmer_john:2sozx:problem
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2sozx:problem [2020/06/06 19:48] 2sozx |
2020-2021:teams:farmer_john:2sozx:problem [2020/06/06 19:51] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | =====fib数列===== | + | [[.problem:fib数列|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$ 显然可以分块计算。 | + | |
2020-2021/teams/farmer_john/2sozx/problem.1591444113.txt.gz · 最后更改: 2020/06/06 19:48 由 2sozx
