矩阵快速幂

· · 个人记录

就是一些转移式，用矩阵快速幂优化一下。

https://vjudge.net/contest/510197#overview

首先，定义矩阵乘法：

对于一个 n\times k 的矩阵 A 和一个 k\times m 的矩阵 B 还有一个矩阵 C=A\times B。那么 C 是一个 n\times m 的矩阵，且 C_{ij}=\sum\limits_{p=1}^kA_{i,p}\times B_{p,j}(i=\overline{1,2,\cdots,n},j=\overline{1,2,\cdots,m})。

然后，因为矩阵乘法满足结合律，所以我们有了矩阵快速幂。矩阵快速幂的话就是把快速幂的板子套在矩阵上而已。

A

已知 f_1=x,f_2=y,f_i=f_{i-1}+f_{i-2}(i>2)，求 f_n。

我们可以尝试推一下转移矩阵 base：

\begin{pmatrix}f_{i-1}+f_{i-2}\\f_{i-1}\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}f_{i-1}\\f_{i-2}\end{pmatrix}

然后快速幂就好了。

B

有 b 个格子，每个格子有 n 个数字，各个格子里面的数字都是相同的. 求从 b 个格子中各取一个数字, 构成一个 b 位数, 使得这个 b 位数模 x 为 k 的方案数（同一格子内相同的数字算不同方案）。

我们设 dp_{i,j} 表示前 i 个格子中取数后，模 x 的结果为 j 的方案数。

递推式也容易推出来：dp_{i,(j\times10+a_k)\bmod x}=\sum dp_{i-1,j}。

但是，这样显然会 TLE。所以我们需要一些优化。

对于每一个 i=\overline{1,2,\cdots,b}，我们可以把 dp_{i,j},j=\overline{0,1,\cdots,x-1} 当做一个状态。然后根据所给的 a 进行转移。然后用矩阵快速幂优化即可。

C

你在 (0,0) 。

在 (x,y) 时，每次移动可以到达 (x+1,y+1),(x+1,y),(x+1,y-1) 。

平面上有 n 条线段，平行于 x 轴，参数为a_i , b_i ,c_i ，表示在 (a_i,c_i) 到 (b_i,c_i) 的一条线段，保证 b_i=a_{i+1}。

要求你一直在线段的下方且在 x 轴上方，即 a_i \leq x \leq b_i 时， 0 \leq y \leq c_i 。

问 : 到达 (k,0) 的方案数，方案数对 10^9+7 取模。

我们设 dp_{i,j} 表示走到 (i,j) 的方案数，k_i 表示 x 坐标为 i 时行动的上界。

按照题意，递推式：

dp_{i,j}=\begin{cases}dp_{i-1,j-1}+dp_{i-1,j}&(j=k_i)\\dp_{i-1,j-1}+dp_{i-1,j}+dp_{i-1,j+1}&(0<j<k_i)\\dp_{i-1,j}+dp_{i-1,j+1}&(j=0)\end{cases}

那么，我们可以构造一个形如 \begin{pmatrix}1&1&0&\cdots&0&0&0\\1&1&1&\cdots&0&0&0\\\vdots&&&\ddots&&&\vdots\\0&0&0&\cdots&1&1&1\\0&0&0&\cdots&0&1&1\end{pmatrix} 的矩阵进行转移。用快速幂优化即可。

D

f_i=1(i<m) f_i=f_{i-1}+f_{i-m}(m\le i)

求 f_n。

用一个 m\times m 的矩阵就可以了。

\begin{pmatrix}f_{i+1}+f_{i-m+1}\\f_{i}\\f_{i-1}\\\vdots\\f_{i-m+1}\end{pmatrix}=\begin{pmatrix}1&0&0&\cdots&0&0&1\\1&0&0&\cdots&0&0&0\\0&1&0&\cdots&0&0&0\\\vdots&&&\ddots&&&\vdots\\0&0&0&\cdots&0&1&0\end{pmatrix}\begin{pmatrix}f_i\\f_{i-1}\\f_{i-2}\\\vdots\\f_{i-m}\end{pmatrix}

E

已知 f_1,f_2,f_3 和 c，f_i=c^{2i-6}f_{i-1}f_{i-2}f_{i-3}(i>3)，求 f_n。

我们可以发现这里不再是加，所以不能直接矩阵快速幂。但是，我们都知道对于一个大于 1 的数 a 有 \log_ax\cdot y=\log_ax+\log_ay，但是，如果用 \log 的话，你的精度爆上个十几遍是不成问题的。所以我们需要在推一推。

f_1=c^0f_3^0f_2^0f_1 f_2=c^0f_3^0f_2f_1^0 f_3=c^0f_3f_2^0f_1^0 f_4=c^2f_3f_2f_1 f_5=c^6f_3^2f_2^2f_1 f_6=c^{14}f_3^4f_2^3f_1^2 f_7=c^{30}f_3^7f_2^6f_1^4 f_8=c^{60}f_3^{13}f_2^{11}f_1^7

我们设 t_{i,j},(i>3,j=\overline{1,2,3}) 表示 f_i 分解过后 f_j 的系数，g_i 表示 f_i 中 c 的系数。我们发现：

t_{i,j}=t_{i-1,j}+t_{i-2,j}+t_{i-3,j} g_i=2i-6+g_{i-1}+g_{i-2}+g_{i-3}

然后就可以用矩阵快速幂推过去了，但是，如果不取模的话，会炸掉，所以我们需要欧拉降幂：

a^b\equiv a^{b\mod\varphi(p)}\pmod{p}

因为本题的模数是给质数，所以对指数的模数为其减一。