矩阵乘法

前置知识多项式除法|取模该部分见 多项式操作 特征值与特征向量（这部分我也不怎么理解，就大概记个结论） 对 $n$ 阶矩阵 $A$ 的特征向量 $\vec{v}$ 与，有特征值 $\lambda$ 满足$$A\vec v = \lambda\vec v$$移项则有 $(\lambda I - A)\vec v = 0$，其中 $I$ 为单位矩阵 那么有解的充要条件是 $det(\lambda I - A) = 0$ 令 $f(\lambda) = det(\lambda I - A)$，即此时可将 $det (\lambda I - A)$ 看作一个 $n$ 阶多项式，则称 $f(\lambda)$ 为矩阵 $A$ 的特征多项式，对矩阵 $A$，其任意特征值 $\lambda_0$ 都满足 $f(\lambda_0) = 0$ $\text{Hamiton-Cayley}$定理对矩阵 $A$ 及其特征多项式 $f(x)$，满足 $f(A) = O$，其中 $O$ 为零矩阵 证明留坑 常系数齐次线性递推求一个满足 $k$ 阶齐次线性递推数列 $h_i$ 的第 $n$ 项，即$$h_n = ...

计数问题也许可以转化为矩阵乘法形式 比如若该题没有不能在一条边上重复走的条件限制，那么直接将邻接矩阵转化为矩阵乘法即可 故 矩阵乘法计数对于计数问题，若可以将 $n$ 个点表示成 $n \times n$ 的矩阵，并且可以保证中途转移对象不会变化，即可用矩阵乘法计数 至于该题那么考虑该题，加入了不能重复在一条边上走的限制，那么最简单的思想就是拆点，并且让改点屏蔽掉当前方向，但是如果考虑边，一条无向边可以拆成两条有向边，那拆出来的就比点少很多了，故考虑点边转化 那么只要在起始点加一条超级源边，同样矩阵乘法即可统计答案 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110#include <io ...

后面发现这是某次考试的原题来着 怕是太久没打过状压然后连 $k \le 5$ 可能要状压这么明显的提示都给无视了然后就随便敲了个矩阵树骗了 $50$。。。 好所以这题是一道状压 令 $state$ 表示对于 $i$ 点（包括它本身）的前 $k$ 个点的连通状态，$e.g. \{1, 1, 2\}$ 表示 $\{1, 2\}, \{3\}$ 点分别连通 注意为了去重要用最小表示，于是即使当 $k = 5$ 时状态数也不过就 $52$ 个而已了 再令 $f_{i, j}$ 表示前 $i$ 个点且 $i$ 点连通状态为 $j$ 时的方案数，$g_{i, j}$ 表示状态 $i$ 转移到状态 $j$ 时的方案数，则有方程$$f_{i, j} = \sum_k f_{i - 1, k} * g_{k, j}$$可以发现这就是一个矩阵转移式，故直接矩阵乘法即可 那么至于计算 $g_{i, j}$ 则枚举 $i$，及当前点与前面点的连通状态 $state$（二进制表示），然后并查集维护一下，判断当前 $state$ 是否会与之前冲突（连边后无环且原状态中的最前点（即会被刷掉的点）与当前的 $k$ ...