[luoguP3317] [SDOI2014]重建（矩阵树定理）传送门为了搞这个题又是学行列式，又是学基尔霍夫矩阵。矩阵树定理本题题解无耻地直接发链接，反正我也是抄的题解。。#include <cstdio>#include <cmath>#include <iostream>us

[POJ2778]DNA Sequence（AC自动机 + DP + 矩阵优化）传送门

AC自动机加DP就不说了
注意到 m <= 10，所以模式串很少。
而 n 很大就需要 log 的算法，很容易想到矩阵。
但是该怎么构建？
还是矩阵 A(i,j) = ∑A(i,k) * A(k,j)，那么i

[luoguP2886] [USACO07NOV]牛继电器Cow Relays（矩阵）传送门

矩阵快速幂，本质是floyd
把 * 改成 + 即可
注意初始化

因为只有100条边，所以可以离散化


#include <cstdio>
#include <cstring>
#include <algorithm>
#define N

[luoguP2461] [SDOI2008]递归数列（DP + 矩阵优化）传送门

本题主要是构造矩阵，我们只需要把那一段式子看成两个前缀和相减， 然后就直接矩阵连乘。

直接对那个k+1阶矩阵快速幂即可，注意初始化矩阵为单位矩阵，即主对角线（左上到

[HDU2157]How many ways??（DP + 矩阵优化）传送门

k < 20
k这么小，随便dp一下就好了。。。
dp[i][j][k]表示从i到j经过k个点的方案数
4重循环。。

但是如果k很大就不好弄了
把给定的图转为邻接矩阵，即A(i,j)=1当且仅

[Vijos1067]Warcraft III 守望者的烦恼（DP + 矩阵优化）传送门

可知
f[i] = f[i 1] + f[i 2] + ... + f[i k]
直接矩阵优化就好了


#include <cstdio>
#include <cstring>
#define p 7777777
#define LL long long

int n,

[luoguP2129] L国的战斗续之多路出击（模拟 || 矩阵）传送门

1.模拟
easy

#include <cstdio>
#define N 500001

int n, m;
int X[N], Y[N], x[N], y[N], a = 1, b = 1, p, q;
char s[N][1];

int main()

for(i = m; i

[POJ3233] Matrix Power Series（矩阵快速幂）传送门

k <= 109 暴力肯定超时
根据矩阵性质，可以发现
S(4) = A1 + A2 + A2* (A1 + A2)
S(5) = A1 + A2 +A2* (A1+ A2) + A5
所以可以递归二分求解，分别判断 Ak，k 为奇数和偶

矩阵运算所满足的定律向量满足一些与加法和乘法相关的结合律、交换律、分配律等，矩阵也满足某些定律，它们是：
（1）A + B = B + A（加法交换律）
（2）A + (B + C) = (A + B) + C（加法结合律）
（3）A*(B*C) = (A*B)*

[luoguP1962] 斐波那契数列（矩阵快速幂）传送门

解析详见julao博客连接worldframe.top/2017/05/10/清单数学方法——矩阵/

——代码


1 #include <cstdio>
2 #include <cstring>
3 #define LL long long
4

[luoguP3390]【模板】矩阵快速幂传送门

模板不解释。

——代码


1 #include <cstdio>
2 #include <cstring>
3 #define LL long long
4
5 int n;
6 LL k;
7 const int p = 1e9 + 7;
8
9 str