矩阵乘法应用

1. Fibonacci Number

【题意简化】求斐波那契数列前 $n(\le 10^{18})$ 项的和,取 $10^9+7$ 的余数。

【分析】由 $f_n=f_{n-1}+f_{n-2}$ 和 $S_{n}=S_{n-1}+f_n$ 可以构造矩阵乘法：

$\begin{bmatrix} S_n \\ f_n\\ f_{n-1} \end{bmatrix}= \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}\begin{bmatrix} S_{n-1} \\ f_{n-1} \\ f_{n-2} \end{bmatrix}$

2. 定长路径条数统计 walk

【题意简化】

给一个 $𝑛(n \le 50)$ 阶有向图，每条边的边权均为 $1$，然后给一个整数 $𝑘(k \le 10^{18})$，你的任务是对于所有点对 $(𝑢,𝑣)$ 求出从 $𝑢$ 到 $𝑣$ 长度为 $𝑘$ 的路径的数量（不一定是简单路径，即路径上的点或者边可能走多次）。

【分析】

当 $k=2$ , 要算所有长度为 $2$ 路径的条数，实际就是枚举 $i$ 到 $j$ 长度为 $2$ 的条数，即从 $i$ 走到 $k$ ，再从 $k$ 走到 $j$ , $a_{ik}$ 就是表示 $i$ 到 $k$ 长度是 $1$ 的方法数，那么长度为 $2$ 的方法数就是 $\sum_{k=1}^{n} a_{ik}*a_{kj}$ , 我们发现了矩阵乘法的影子，对于邻接表 $A$ , $A^2$ 就是 $\sum_{k=1}^{n} a_{ik}*a_{kj}$ ，依次类推长度为 $3$ 就是 $A^3$ , 长度为 $k$ 就是 $A^k$.

利用矩阵快速幂，求出 $A^k$ , 要枚举所有起点终点，最后要求 $\sum_{i=1}^{n}\sum_{j=1}^{n} a'_{ij}$ ,其中 $a'_{ij}$ 代表 $A^k$ 第 $i$ 行第 $j$ 列值。

参考代码：点击

3. 定长最短路 [USACO07NOV] Cow Relays G

【题意简化】

给你一个 $𝑛(n\le 100)$ 阶加权有向图和一个整数 $𝑘(k \le 10^{18})$。对于每个点对 $(𝑢,𝑣)$ 找到从 $𝑢$ 到 $𝑣$ 的恰好包含 $𝑘$ 条边的最短路的长度。（不一定是简单路径，即路径上的点或者边可能走多次）

【分析】 广义矩阵乘法，也是 动态DP 基础。

我们可以构造图的领接矩阵 $G$, $G_{ij}$ 表示表示 $i$ 到 $j$ 的边权，如果没有变，$G_{ij}=\infty$ (有重边的情况取边权最小值)。对于 $k=2$ 的情况，转移方程就是

$L_{k=2}[i,j]=\min_{1\le p \le n}\{G[i,p]+G[p,j]\}$

进而可以得到

$L_{k+1}[i,j]=\min_{1\le p \le n}\{L_k[i,p]+G[p,j]\}$

类比矩阵乘法，我们我们发现上述转移只是矩阵乘法的乘积求和编程相加取最小值，可以重新定义矩阵乘法，得到广义矩阵乘法 $\odot$ ，即 $A\odot B=C$ 表示

$$C[i,j]=min_{1\le p \le n}\{A[i,p]+B[p,j]\}$$

于是有

$$L_{k+1}=L_{k}\odot G$$

展开得到

$L_{k}=G \odot \dots \odot G=G^{\odot k}$

具有结合律，可以使用矩阵快速幂求解，时间复杂度为 $O(n^3\log{k})$

4. P5364 [SNOI2017]礼物

【题意简化】

第一个朋友会带给他 $1$ 个大香蕉，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 $K$ 次方那么多个。已知 $N(\le 10^{18}),K(\le 10)$ , 请输出第 $N$ 个朋友送的礼物个数对 $10^9+7$ 取模的结果。

【分析】

根据题意设 $f_i$ 表示第 $i$ 个小朋友的礼物数量，可以得到：

$f_i=(\sum_{j=1}^{j \le i-1} f_j)+i^k$,设$S_i=\sum _{j=1}^{j\le i}f_j$ , 可以得到

$S_i=S_{i-1}+f_i=2S_{i-1}+i^k$

$k$比较小，可得：

$(i+1)^k=C_k^ki^k+C_k^{k-1}i^{k-1}+...+C_k^0i^0$

可以构造矩阵乘法：

$\begin{bmatrix} S_{i-1}&i^k&i^{k-1}&...&i^0 \end{bmatrix} \begin{bmatrix} 2 & 0 & 0 & 0 & . & 0 \\ 1 & C_k^k & 0 & 0 & . & 0\\ 0 & C_k^{k-1}& C_{k-1}^{k-1} & 0 & . & 0\\ 0 & C_k^{k-2}& C_{k-1}^{k-2} & C_{k-2}^{k-2} & . &0 \\ . & . & . & . & . & \\ 0 & C_k^{0} & C_{k-1}^{0} & C_{k-2}^{0} & . & C_0^0 \end{bmatrix}$

=$\begin{bmatrix} S_{i}&(i+1)^k&(i+1)^{k-1}&...&(i+1)^0 \end{bmatrix}$

$ans=S_n-S_{n-1}$

参考代码：点击

5. [THUSC 2017] 大魔法师

6. LOJ 6208 树上询问

---

其他题目

1. P10502 Matrix Power Series

2. Hdu5171 小奇的集合

3. POJ - 2440 DNA

4. HDU - 2256

---

学习完毕

{{ select(1) }}

• YES
• NO