解决的问题 博客 洛谷专栏 矩阵乘法在图论中常用于(定长/限制类)路径统计和最短路问题。此类型题目的时间复杂度往往是 $O(n^3 \log k)$，故此类题目的点数不应过大。 OI-wiki 一些代码技巧 struct Mat { int n; vector<VI> A; vector<int>& operator…

题单 我也不知道为什么下划线一多 Latex 就要崩掉，我已经不想管了。 CSES - 1075 Permutations II 动态规划好题。 解法一（recommend) 定义 $F(i, j, k)$ $1$ 表示在 1 到 $i$ 的排列中，满足有 $j$ 对相邻的 $<i$ 的差为 $1$，$k = 1$ 或 $0$ 分别对应 $i…

数据结构（线段树为主） 题单 P6569 [NOI Online #3 提高组] 魔法值 首先看题目数据范围，$n \leq 100$ ，这种情况要么说明这道题的时间复杂度是比较高的，要么就和矩阵乘法脱不开关系。 阅读题目之后，我们发现可以应用 Floyd 最短路，也就是矩阵乘法的思想去描述每一轮每一个城市的魔法值。 故这道题应该先用邻接矩阵建图，…