矩阵树定理 + BEST定理
矩阵树定理 + BEST定理
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135639913
行列式性质：
交换两行，符号取反
一行整体加上另一行的 倍，行列式不变
求一个图的内向生成树个数：
令度数矩阵为 ，邻接矩阵为 。设 ， 去掉一行一列的行列式即为答案，我们设为 。
求一个欧拉图的欧拉回路个数，我们有结论：
如果每个点最后走的一条出边形成一棵内向树，则剩下的边任意走都是合法的欧拉路径（前提：图是欧拉图）
所以一个图的欧拉回路个数为：
如果我们求本质不同欧拉回路个数，我们除个 即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-09-27
线性代数+分治：446E
线性代数+分治：446E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133336367 https://codeforces.com/problemset/problem/446/E 把官方题解翻译了一遍 考虑暴力，肯定想到dp，然后变成矩阵。设 用 代替 （这样子数之间的差值不会变化，但对于问题的处理能方便很多） 我们先令（也就是初始时的方案数） ，然后尝试构造转移矩阵 BBB BBB 的大小应该为 n×nn\times nn×n ，每个格子对...
2023-09-20
线段树维护矩阵：0920T4
线段树维护矩阵：0920T4 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133100771 正解为文艺平衡树维护矩阵，但我打不动，所以打了部分分 首先可以写成dp形式 然后又可以写成矩阵形式 然后矩阵显然支持结合律 所以可以拿线段树维护 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596...
2023-09-30
贪心找性质+DP表示+矩阵表示+线段树维护：CF573D
贪心找性质+dp表示+矩阵表示+线段树维护：CF573D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133437456 比较套路的题目 首先肯定贪心一波，两个都排序后尽量相连。我一开始猜最多跨1，但其实最多跨2，考虑3个人的情况： 我们发现第3个人没了，所以可以出现跨2的情况 然后直接上dp，由 i−1,i−2,i−3i-1,i-2,i-3i−1,i−2,i−3 转移过来。 然后这显然可以拿矩阵表示。 然后显然可以拿线段树维护。 后面三部分都是比较套路...
2023-09-27
贪心+二分+DP+矩阵快速幂：CF461E
贪心+二分+DP+矩阵快速幂：CF461E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133316261 https://codeforces.com/contest/461/problem/E 第一步：捕捉题目信息 四种字符 →\to→ 矩阵 n≤1018→n\le 10^{18}\ton≤1018→ 矩阵快速幂 →\to→ dp 最小值最大 →\to→ 二分 第二步：分析性质 sss 未知？那如果已知怎么做，肯定是每次暴力选最长的。 ...
2023-12-25
猜结论 + bitset优化高斯消元：CF1070L
猜结论 + bitset优化高斯消元：CF1070L 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135202185 https://www.luogu.com.cn/problem/CF1070L 所有点度数为偶，则答案为1. 此时可以猜结论，猜测答案最多为2. 如果答案为2，看一下充要条件是什么。划分为两个集合（注意可以不连通），其中一个 xi=1x_i=1xi=1 ，另一个为0. 如果本身度数为偶，则是 ⊕xj=0\oplus x_j=0⊕xj=...
2026-06-19
线性代数学习笔记（第 6- 10 课）
线性代数学习笔记（第 6- 10 课） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162126613 线性代数学习笔记（6-10课） 第六课：分块矩阵 I 分块运算的规则 分块矩阵 运算规则 加法 乘法 前提： AAA 的列分发和 BBB 的行分法必须完全相同 II 分块对角阵的性质 定义：一个分块矩阵除了主对角线上的子块外，其余所有子块都是零矩阵 形式： 性质： 行列式等于对角块行列式之积 逆矩阵等于对角块逆矩阵的分...