Start

题目输出长这样：

Here is the fibonacci chall 1, please solve it

fib(0, p) = (0, 1)
fib(1, p) = (1, 1)
...
fib(n, p) = (a, b)
fib(n + 1, p) = (b, (a + b) % p)


Round 1/10

now you know:
p = 5
k = 7
fib(a, p) = (1, 2)
fib(b, p) = (2, 3)

if answer is (k1, k2), please give me k1 * p + k2
Here is the question:
fib(a + b, p) =
fib(ka, p) = 
if fib(a + c, p) = (0, 1), fib(c, p) = 

（数据改掉了：数据很大，我塞不下）

一共 10 Round，每个 Round 有 3 个 case（其实做完一整个之前不知道有几个 case）

可以看见这个题一直都是模 $p$ 意义下，都是同余式，能线性运算；
那接下来的分析就不管 $p$ 了，$Fib\left(n, p\right)$ 也写成 $F_n$ 好了，写代码的时候加减乘记得模一下 $p$

我们知道斐波那契数列 $\left\{ f_n \right\}$ 满足 $f_0 = 0$，$f_1 = 1$，$f_n = f_{n-1} + f_{n-2}$

那题目里的 $F_n$ 的意思其实就是 $\begin{bmatrix} f_n & f_{n+1} \end{bmatrix}$

然后这个递推式用矩阵可以写成这样

$$ \begin{equation} \begin{bmatrix} f_n \\ f_{n+1} \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} f_{n-1} \\ f_n \end{bmatrix} \end{equation} $$

所以还有这个

$$ \begin{equation} \begin{bmatrix} f_{n-1} & f_n\\ f_n & f_{n+1} \end{bmatrix} = \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix}^n \end{equation} $$

Case 1

已知 $F_a$ 和 $F_b$ 要求 $F_{a+b}$

由 $(1)$ 式递推知

$$ \begin{bmatrix} f_{n+b} \\ f_{n+b+1} \end{bmatrix} = \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix}^b \begin{bmatrix} f_{n} \\ f_{n+1} \end{bmatrix} $$

用 $(2)$ 式把中间那个幂换掉

$$ \begin{bmatrix} f_{n+b} \\ f_{n+b+1} \end{bmatrix} = \begin{bmatrix} f_{b-1} & f_b\\ f_b & f_{b+1} \end{bmatrix} \begin{bmatrix} f_{n} \\ f_{n+1} \end{bmatrix} $$

即

$$ \begin{equation} \begin{bmatrix} f_{a+b} \\ f_{a+b+1} \end{bmatrix} = \begin{bmatrix} f_{b-1} & f_b\\ f_b & f_{b+1} \end{bmatrix} \begin{bmatrix} f_{a} \\ f_{a+1} \end{bmatrix} \end{equation} $$

Case 2

已知 $F_a$ 和 $k$ 要求 $F_{ka}$

由 $(3)$ 有

$$ \begin{bmatrix} f_{2a} \\ f_{2a+1} \end{bmatrix} = \begin{bmatrix} f_{a-1} & f_a\\ f_a & f_{a+1} \end{bmatrix} \begin{bmatrix} f_{a} \\ f_{a+1} \end{bmatrix} $$

$$ \begin{bmatrix} f_{3a} \\ f_{3a+1} \end{bmatrix} = \begin{bmatrix} f_{a-1} & f_a\\ f_a & f_{a+1} \end{bmatrix} \begin{bmatrix} f_{2a} \\ f_{2a+1} \end{bmatrix} $$

$$ \begin{bmatrix} f_{4a} \\ f_{4a+1} \end{bmatrix} = \begin{bmatrix} f_{a-1} & f_a\\ f_a & f_{a+1} \end{bmatrix} \begin{bmatrix} f_{3a} \\ f_{3a+1} \end{bmatrix} $$

$$\cdots$$
所以

$$ \begin{bmatrix} f_{ka} \\ f_{ka+1} \end{bmatrix} = \begin{bmatrix} f_{a-1} & f_a\\ f_a & f_{a+1} \end{bmatrix}^{k-1} \begin{bmatrix} f_{a} \\ f_{a+1} \end{bmatrix} $$

Case 3

已知 $F_a$，还知 $F_{a+c} = \begin{bmatrix} 0 & 1 \end{bmatrix}$，求 $F_c$

这是第一问反过来了

由 $(3)$ 知道

$$ \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} f_{a-1} & f_a\\ f_a & f_{a+1} \end{bmatrix} \begin{bmatrix} f_c \\ f_{c+1} \end{bmatrix} = \begin{bmatrix} f_{c-1} & f_c\\ f_c & f_{c+1} \end{bmatrix} \begin{bmatrix} f_a \\ f_{a+1} \end{bmatrix} $$

这里我们想要 $F_c$，当然是考虑这个

$$ \begin{equation} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} f_{a-1} & f_a\\ f_a & f_{a+1} \end{bmatrix} \begin{bmatrix} f_c \\ f_{c+1} \end{bmatrix} \end{equation} $$

因为这个可以两边左乘 $\begin{bmatrix} f_{a-1} & f_a\\f_a & f_{a+1} \end{bmatrix}$ 的逆矩阵，于是右边直接就是答案了

然后它的逆矩阵是

$$ \frac{\begin{bmatrix} f_{a+1} & -f_a\\ -f_a & f_{a-1} \end{bmatrix}}{\begin{vmatrix} f_{a-1} & f_a\\ f_a & f_{a+1} \end{vmatrix}} = (-1)^a {\begin{bmatrix} f_{a+1} & -f_a\\ -f_a & f_{a-1} \end{bmatrix}} $$

（这里我用了一个小寄巧，就是下面这个）

$$ \begin{bmatrix} f_{n-1} & f_n\\ f_n & f_{n+1} \end{bmatrix} = \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix}^n $$

$$ \Longrightarrow \begin{vmatrix} f_{n-1} & f_n\\ f_n & f_{n+1} \end{vmatrix} = \begin{vmatrix} 0 & 1\\ 1 & 1 \end{vmatrix}^n = (-1)^n $$

于是最终有

$$ \begin{bmatrix} f_c \\ f_{c+1} \end{bmatrix} =(-1)^a {\begin{bmatrix} f_{a+1} & -f_a\\ -f_a & f_{a-1} \end{bmatrix}} \begin{bmatrix} 0 \\ 1 \end{bmatrix} $$

啊，不过我不知道 $(-1)^a$ 的符号耶，我又不知道 $a$ 是多少！

1. 其实不用知道，分类讨论出来两个解，代回 $(4)$ 去验算一下，哪个解对就要哪个就可以了
2. 马后炮：不用小寄巧，其实 $\begin{vmatrix}f_{a-1} & f_a\\ f_a & f_{a+1}\end{vmatrix} = f_{a-1}f_{a+1} - f_a^2$ 就好（

Show me the code

怎么感觉这就是个数学题，代码好像不是重点

NumPy 他奶奶的爆 int，所以我只好手写了基本的矩阵乘法和快速幂

下崽：fib1.zip