\[\begin{bmatrix} a & b \\ c & d \end{bmatrix} \]
矩阵乘法
基础部分
e.g.
\[\begin{bmatrix} a_{1, 1} & a_{1, 2} \\ a_{2, 1} & a_{2, 2} \end{bmatrix} \begin{bmatrix} b_{1, 1} & b_{1, 2} \\ b_{2, 1} & b_{2, 2} \end{bmatrix} = \begin{bmatrix} a_{1, 1} b_{1, 1} + a_{1, 2} b_{2, 1} & a_{1, 1} b_{1, 2} + a_{1, 2} b_{2, 2} \\ a_{2, 1} b_{2, 1} + a_{2, 2} b_{2, 1} & a_{2, 1} b_{1, 2} + a_{2, 2} b_{2, 2} \end{bmatrix} \]规则
第一个矩阵的列数必须等于第二个矩阵的行数。
运算律
- \(A \times B ≠ B \times A\)
-
\(A\times B \times C=A\times(B\times C)\)
这条性质也是矩阵快速幂的前提
将 \(O(n)\) 的程序通过矩阵优化转化至矩阵快速幂，变成 \(O(k^3\log n)\) 的复杂度（\(k\) 是矩阵大小）。
例题——矩阵加速数列生成
P1962 斐波那契数列
\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} \times \begin{bmatrix} F_n \\ F_{n - 1} \end{bmatrix} = \begin{bmatrix} F_n + F_{n - 1}\\ F_{n} \end{bmatrix} \]\[设ANS= \begin{bmatrix} 1 \\ 1 \end{bmatrix}，则 \ \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}^{n-2} \times ANS = \begin{bmatrix} F_n \\ F_{n - 1} \\ \end{bmatrix} \]P2044 [NOI2012] 随机数生成器
\[\begin{bmatrix} X_n & c\\ 0 & 0 \end{bmatrix} \times \begin{bmatrix} a & 0 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} a X_n+c & c \\ 0 & 0 \end{bmatrix} \]矩阵快速幂优化 dp
P5343【XR-1】分块
令可行的块长为 \(a_1, a_2, \dots,a_m\)，则转移方程显然：
\[f_i=\sum^m_{j=1}f_{i-a_j} \]但是显然这个复杂度是不可接受的，所以我们考虑优化。
考虑到块长的范围只有 \(100\)，可以利用矩阵快速幂加速解决本题。
令 \(x\) 表示可行的块长中最长的
设状态矩阵为
\[\begin{bmatrix} f_x\\ f_{x-1}\\ f_{x-2}\\ \vdots\\ f_3\\ f_2\\ f_1 \end{bmatrix} \]要转移到
\[\begin{bmatrix} f_{x+1}\\ f_{x}\\ f_{x-1}\\ \vdots\\ f_4\\ f_3\\ f_2 \end{bmatrix} \]我们要构造一个 \(m\times m\) 的矩阵来转移
首先，也是一般矩阵加速 dp 的相通之处，观察到 \(f_2\) 到 \(f_{x}\) 这部分是不变的，那么我们可以先向转移矩阵内填入：
\[\begin{bmatrix} \\ 1 & 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 1 & 0 & \dots & 0 & 0& 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 0 & 0 & \dots & 1 & 0 & 0\\ 0 & 0 & 0 & \dots & 0 & 1 & 0\\ \end{bmatrix} \]思考第一行填入什么，观察状态转移方程得，\(f_{x+1}\) 应该由 \(f_{x+1-a_1},f_{x+1-a_2},\dots,f_{x+2-a_m}\) 转移而来，所以矩阵的第一行显而易见是：
\(a_i\) 处填 \(1\)，其余地方填 \(0\)。
可得
\[\begin{bmatrix} \\ 1 & 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 1 & 0 & \dots & 0 & 0& 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 0 & 0 & \dots & 1 & 0 & 0\\ 0 & 0 & 0 & \dots & 0 & 1 & 0\\ \end{bmatrix} ^{n-m+1}\times \begin{bmatrix} f_{x - 1}\\ f_{x-2}\\ f_{x-3}\\ \vdots\\ f_2\\ f_1\\ f_0 \end{bmatrix} = \begin{bmatrix} f_{n}\\ f_{n-1}\\ f_{n-2}\\ \vdots\\ f_{n-m+3}\\ f_{n-m+2}\\ f_{n-m+1} \end{bmatrix} \]快速幂转移即可，最终答案是答案矩阵的最上方
\(\color{red}{\texttt{记得开 long long}}\)
P3758 [TJOI2017]可乐
考虑一个更一般的情况，给定一张 \(n\) 个点无边权有向图，问从 \(s\) 经过 \(k\) 条边走向 \(t\) 的方案总数？
设矩阵 \(A\) 是这张图的邻接矩阵，则 \(A^k\) 中 \(a_{i,j}\) 表示 \(i\) 到 \(j\) 经过 \(k\) 条边的行进路线种数，理解见下：
令 \(B=A^p\)，\(C=A^q\)，\(R=B\times C=A^{p+q}\)，则根据矩阵乘法的定义，
\[R_{i,j}=\sum_{k=1}^n A_{k, j}B_{i,k}=\sum_{k=1}^n B_{i,k}A_{k, j} \]显然结论是正确的。可以通过矩阵快速幂加速。
再回到这道题上，在原地停留显然可以自环，而自爆可以看作连一条通向 \(n+1\) 的单向边，也就是说去了另一个世界（雾
代码就十分简单了。
P3977 [TJOI2015]棋盘
这篇文章是给像我一样初学矩阵优化 dp，然后看其他大佬写的题解看的一脸雾水的蒟蒻看的，所以比较详细，语文水平不好还请多多包涵
先用状压 dp 的思路分析，每一行的摆放状态可以压成一个二进制数，根据给出矩阵的第二行可以预处理出每一行合法的状态集合 \(S\)，再 dfs / 瞎搞出相邻行的合法转移，设 \(f_{i,sta}\) 表示第 \(i\) 行的状态是 \(sta\) 时的方案总数，\(check_{sta,nxt}\) 表示上一行的状态为 \(sta\)，下一行的状态为 \(nxt\) 是否合法，则转移方程显然：
\[f_{i,sta}=\sum_{pre\in S} check_{pre,sta}f_{i-1, pre} \]问题是，这样转移的时间复杂度为 \(O(n2^{2m})\)，大概是在 4e9 的级别，无法接受。
注意到每一层的转移都是相同的，于是我们可以考虑用矩阵快速幂优化。
为了方便描述，我们将 \(S\) 构成的序列称作 \(p_1, p_2, \dots, p_{size}\)，设矩阵 \(A^k\) 中 \(a_{i,j}\) 表示状态 \(a_i\) 经过 \(k\) 行转移到状态 \(a_j\) 的方案总数，则初始矩阵为
\[a_{i,j} = check_{p_i,p_j} \]再来看转移矩阵，考虑等式 \(A^p\times A^q=A^{p+q}\)，令 \(B=A^q\)，\(C=A^{p+q}\)，则我们想做到 \(c_{i,j}=\sum^{size}_{k=1}a_{i,k}b_{k,j}\)，注意到这个式子恰好符合矩阵乘法的定义，所以转移矩阵与初始矩阵相同，接下来矩阵快速幂即可。
注意到第 \(1\) 行到第 \(n\) 行转移了 \(n-1\) 次，所以指数要等于 \(n-1\)。
Code
#include<bits/stdc++.h>
#define int unsigned int
const int maxn = 1000006, maxm = 6;
int n, m, p, K, len, siz;
int att[3];
std :: vector<int> fst;
int cal(int x, int p, int ik) {
if(p <= ik)
return x << (ik - p);
return x >> (p - ik);
}
bool check(int x) {
int tmp = x;
for(int i = 0; tmp >> i; ++ i) {
if((x & (1 << i)) == 0) continue;
if((x & cal(att[1], p, i + K)) & ((len - 1) ^ (1 << i)))
return false;
}
return true;
}//一行内是否合法
bool con(int x, int y) {
x ^= y ^= x ^= y;
int tmp = x;
for(int i = 0; i < m; ++ i) {
if((x & (1 << i)) == 0) continue;
if(y & cal(att[2], p, i + K))
return false;
}
tmp = y;
for(int i = 0; i < m; ++ i) {
if((y & (1 << i)) == 0) continue;
if(x & cal(att[0], p, i + K))
return false;
}
return true;
}//相邻两行是否合法
struct matrix {
int m[(1 << maxm) + 5][(1 << maxm) + 5], a, b;
matrix (int x, int y) {
a = x; b = y;
for(int i = 1; i <= a; ++ i)
for(int j = 1; j <= b; ++ j)
m[i][j] = 0;
}
matrix friend operator * (matrix x, matrix y) {
matrix ans(x.a, y.b);
for(int i = 1; i <= x.a; ++ i)
for(int k = 1; k <= y.a; ++ k) {
int s = x.m[i][k];
for(int j = 1; j <= y.b; ++ j)
ans.m[i][j] = (ans.m[i][j] + s * y.m[k][j]);
}
return ans;
}
};
matrix ksm(matrix base, int p) {
matrix res(siz, siz);
for(int i = 1; i <= siz; ++ i) res.m[i][i] = 1;
while(p) {
if(p & 1) res = base * res;
base = base * base; p >>= 1;
}
return res;
}
signed main() {
std :: cin >> n >> m >> p >> K; ++ K;
len = 1 << m;
for(int i = 0; i < 3; ++ i)
for(int j = 1, tmp; j <= p; ++ j)
att[i] <<= 1, std :: cin >> tmp, att[i] |= tmp;
fst.push_back(0x7fffffff);
for(int i = 0; i < len; ++ i)
if(check(i)) fst.push_back(i);
siz = fst.size() - 1;
matrix zy(siz, siz);
for(int i = 1; i <= siz; ++ i)
for(int j = 1; j <= siz; ++ j)
if(con(fst[i], fst[j]))
zy.m[i][j] = 1;
matrix res = ksm(zy, n - 1);
int ans = 0;
for(int i = 1; i <= siz; ++ i) {
for(int j = 1; j <= siz; ++ j)
ans += res.m[i][j];
}
std :: cout << ans;
return 0;
}
P3216 [HNOI2011]数学作业
设 \(f_i\) 为 \(1 ∼ i\) 连起来得到的数，则显然可以得到：\(f_i=f_{i-1}\times cnt(i)+i\)，其中 \(cnt(i)\) 表示 \(i\) 的位数，可以发现对于位数相同的数来说，这个转移方程是固定的，于是考虑用矩阵优化：对于位数为 \(k\) 的数，有如下转移：
\[\begin{bmatrix} 10^k & 1 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} f_i\\ i\\ 1 \end{bmatrix} = \begin{bmatrix} f_{i+1}\\ i+1\\ 1 \end{bmatrix} \]分段转移即可。
标签：dots,begin,end,矩阵,bmatrix,相关,vdots From： https://www.cnblogs.com/8atemak1r/p/16736608.html