省选 数学

直接对除法取模会出错，需要变成 \(((a\mod p)\times (\frac{1}{b}\mod p))\mod p\) 的形式。

性质：两个对 \(p\) 同余的数加减乘上同一个数后依然对 \(p\) 同余。

矩阵乘法：\(c_{i,j}=\sum\limits_1^ka_{i,k}\times b_{k,j}\)。

单位矩阵：对角线上为 \(1\) 的矩阵。

注意，只有 \(n\times n\) 的矩阵才能自乘。

矩阵快速幂加速递推

对于线性递推公式 \(f(F_{i-1},F_{i-2},\cdots,F_{n-k})\)，可以利用矩阵快速幂加速递推。

警钟长鸣：矩阵乘法没有交换律

P1939，注意取模。

P1306

\(\gcd(f_n,f_m)=f_{\gcd(n,m)}\)

首先我们需要知道 \(\gcd(a,b)=\gcd(b,a%b)\)。（欧几里得算法）

我们还需要知道 \(\gcd(a,b)=\gcd(b,a-b)\)。（更相减损术）

引理：\(\gcd(f_n,f_{n+1})=1\)。

\(\gcd(f_n,f_{n+1})=\gcd(f_n,f_{n-1})=\gcd(f_{n-2},f_{n-1})=\cdots=\gcd(f_1,f_2)=1\)

引理二：\(f_m=f_{m-n-1}\times f_n+f_{m-n}\times f_{n+1}\)。

令 \(f_n=a,f_{n+1}=b\)，则 \(f_{n+2}=a+b,f_{n+3}=a+2b,f_{n+4}=2a+3b\)，数学归纳法容易得出 \(f_m=f_{m-n-1}\times a+f_{m-n}\times b\)。

所以 \(\gcd(f_n,f_m)=\gcd(f_n,f_{m-n-1}\times f_n+f_{m-n}\times f_{n+1})\)。

因为 \(f_n|f_{m-n-1}\times f_n\)，利用更相减损术可知 \(\gcd(f_n,f_m)=\gcd(f_n,f_{m-n}\times f_{n+1})\)。

根据引理一，可得 \(\gcd(f_n,f_m)=\gcd(f_n,f_{m-n})\)，可以从因子集合的角度看这一步转化。

然后发现 \(\gcd(f_n,f_m)=\gcd(f_n,f_{m \% n})\)。

递归发现本质上就是求 \(\gcd(n,m)\)，因此 \(\gcd(f_n,f_m)=\gcd(f_{\gcd(n,m)})\)。

总之直觉上看证明好像是对的。

所以矩阵快速幂加速递推求出 \(f_{\gcd(n,m)}\) 即可。

小 trick：若线性递推式为 \(f(F_x,F_y,\cdots,F_z)\)，其中 \(x>y>\cdots>z\)，则矩阵快速幂的指数为 \(n-z\)。

P2044

如果递推式中有常数项，则也要将常数项加入矩阵

为什么？显然矩阵乘法得到的一个结果就是递推式这个多项式中的一项。

龟速乘：一次乘法的时间复杂度为 \(\log\)，但不会爆空间。