都快csps了，还什么都不会的菜鱼（我估计着马上就可以改了这句话了，成了都快noip了）
矩阵
我们要用矩阵优化dp，首先要知道矩阵是个什么东西（感觉其实可以不用知道）。
矩阵的很多定义啥的都可以选择去oi-wiki上去进行学习。很简单的一堆定义。读者自学不难，这里就不多赘述。
矩阵加法
就是将对应 \(A\) 和 \(B\) 两个矩阵对应位置相加。然后得到 \(C\) 这个矩阵。
矩阵乘法
这里大概讲一下矩阵乘法的原理：（突然学了，这里说的好像是内积，外积没见过用（逃）
我们会由一个 \(a \times b\) 的矩阵和一个 \(b \times c\) 的矩阵得到一个 \(a \times c\) 的矩阵。这个时候我们是将左边两个黄色的矩阵每一项相乘然后相加得到了右边矩阵的黄色位置，其他位置亦然，读者自想不难。
一个重要的性质：矩阵乘法是符合结合律的，这也是为什么我们可以用快速幂去优化dp
矩阵求逆
我们有时候会用到一个矩阵的逆矩阵，这个时候我们就要去思考如何计算出来这个逆矩阵。
我们通常是在我们的矩阵右边拼上一个单位矩阵，然后用高斯消元的方法，将左边的原矩阵，变成一个单位矩阵，此时我们右边得到的就是我们的原矩阵的逆矩阵。
矩阵除法
我们将我们要除以的矩阵转换为它的逆矩阵（类比逆元），这个时候再对他进行矩阵乘法。
矩阵求最大最小（这个名字是我自己取的）（貌似已经名算有主，叫做广义矩阵乘法）
感觉矩阵里面可能并没有这个操作，但是我们在优化dp的时候难免不会少了这种求最大最小的动规形式，所以就单独拎出来说一下，也就当作矩阵的一个基本运算吧（辉算？还是carp算）找到题目了再upd（逃
广义矩阵乘法的 \(A \times B = C\)为：
\[C_{i, j} = max_{k=1}^{n}(A_{i, k} + B_{k, j}) \]广义矩阵乘法是具有结合律的，所以也可以用矩阵快速幂来进行优化，
先放个板子
之后再根据例题看怎么应用。
code
struct Matrix
{
ll a[N][N];
inline void init() { memset(a, 0, sizeof a); }
Matrix operator +(const Matrix &x) const
{
Matrix res;
fos(i, 0, N)
fos(j, 0, N)
res.a[i][j] = (a[i][j] + x.a[i][j]) % P;
return res;
}
Matrix operator -(const Matrix &x) const
{
Matrix res;
fos(i, 0, N - 1)
fos(j, 0, N - 1)
res.a[i][j] = (a[i][j] - x.a[i][j]) % P;
return res;
}
Matrix operator *(const Matrix &x) const
{
Matrix res;
fos(i, 0, N - 1)
fos(k, 0, N - 1)
fos(j, 0, N - 1)
res.a[i][j] = (res.a[i][j] + (a[i][k] * x.a[k][j]) % P) % P;
return res;
}
Matrix operator ^(ll k) const
{
Matrix ans, base;
fos(i, 0, N - 1) res.a[i][i] = 1;
fos(i, 0, N - 1)
fos(j, 0, N - 1) base.a[i][j] = a[i][j] % P;
while(k)
{
if(k & 1) res = res * base;
base = base * base;
k >>= 1;
}
return res;
}
} ans, base;
矩阵优化dp的适用范围
基本上就是对于一个线性递推式，我们构造一个答案矩阵，再构造一个转移矩阵，每次将这个转移矩阵进行快速幂，然后我们用答案矩阵去乘转移矩阵，具体就是一个快速幂的实现。
例题
举个很板的栗子。
斐波那契数列
我们都知道斐波那契数列里面有这个递推式
\[f_i = f_{i -1} + f _ {i - 2} \]这个时候我们就可以用上面矩阵乘法的思路来进行求解：
step 1 ： 构造一个答案矩阵 \(\begin{bmatrix} f_{1} & f_{2} & f_{3}\end{bmatrix}\)
step 2 ： 我们还需要构造一个转移矩阵，这个转移矩阵就是依据我们的上面的线性递推式得出来的。 \(\begin{bmatrix} 0 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}\)
step 3 ： 接下来就是进行一个快速幂的计算。进行多少次，取决于你希望让这个答案的位置位于我们这个答案矩阵的第几个位子，若让我们的答案为答案矩阵的第二项，我们将进行 \(n - 2\) 次变换，然后得到 \(\begin{bmatrix} f_{n - 1} & f_{n} & f_{n + 1} \end{bmatrix}\)。
code
const ll N = 3, P = 1e9 + 7;
ll n;
struct Matrix
{
ll a[N][N];
Matrix operator *(const Matrix &x) const
{
Matrix res;
memset(res.a, 0, sizeof res.a);
fos(i, 0, N - 1)
fos(k, 0, N - 1)
fos(j, 0, N - 1)
res.a[i][j] = (res.a[i][j] + (a[i][k] * x.a[k][j]) % P) % P;
return res;
}
} ans, base;
inline void init()
{
base.a[1][0] = base.a[1][2] = base.a[2][1] = base.a[2][2] = 1;
ans.a[0][0] = ans.a[0][1] = 1, ans.a[0][2] = 2;
}
inline void qmi(ll k)
{
while(k)
{
if(k & 1) ans = ans * base;
base = base * base;
k >>= 1;
}
}
int main()
{
read(n); init();
if(n <= 2) {puts("1"); return 0;}
ll k = n - 2;
qmi(k);
cout << ans.a[0][2] << endl;
return 0;
}
但是我们发现，我们构造出来的转移矩阵中，第一横行都为 \(0\)，所以我们就可以考虑，省去一维。
新的答案矩阵 \(\begin{bmatrix}f_1 & f_2\end{bmatrix}\)，新的转移矩阵为 \(\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}\)。剩下的代码读者自己实现不难。
T1
这个可以作为一个很好的练习题，既不难，又可以检验之前学会了没有。
这个时候我们知道了广义斐波那契数列的递推式：
\[f_{i} \gets p \times f_{i - 1} + q \times f_{i - 2} \]还是和上面的步骤一样，构造矩阵，然后转移。
不难得出我们的答案矩阵为 \(\begin{bmatrix} f_{1} f_{2}\end{bmatrix}\) ，但是由于我们的递推式的不同，我们的转移矩阵将变成 \(\begin{bmatrix} 0 & q \\ 1 & p \end{bmatrix}\)
之后即是相同的矩阵快速幂。
这个题目用来做一个提升感觉并不为过。
这个题目我们将会用到一种技巧，因为我们在转移的时候不是仅仅只有 dp 数组的转移，还要考虑带个常数，所以说我们会采取一个扩维的方法，单独扩出来一维，放上 1，然后转移我们那个拼接的数字。
之后就是我们的转移方程了（不会有人不会推吧）：
\[f_{i} = f_{i-1} * 10 ^ {\lfloor {\log_{10} i} \rfloor + 1} + i \]\[\begin{bmatrix} f_i \\ i \\ 1 \end{bmatrix} = \begin{bmatrix} f_{i - 1} \\ i - 1 \\ 1\end{bmatrix} \times \begin{bmatrix} 10 ^ {\lfloor\log_{10} i \rfloor} + 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix} \] 标签：Matrix,fos,res,矩阵,base,bmatrix,优化,dp From： https://www.cnblogs.com/carp-oier/p/17765387.html