标签-矩阵

题意给出一个 $N$ 点有向图,从 $1$ 到 $N$ ,要求恰好 $T$ 时刻到达。其中 $N\le 10$ ,边权 $\in[1,9]$ 。边权为 $0$ 代表没有边。题解考虑边权只可能为 $1$ 的情况。用 $f[i][j]$ 代表 $i\rightarrow j$ 恰好 $T$ 时刻到达的方案数,那么$$f_T[i][j]=\sum_{k=1}^{N} f_{T-1}[i][k]\t...
access_time    bookmark 题解    comment 0 条评论
省选/NOI-
题意求不包含子串 $A$ 的长度为 $N$ 的数字 $X$ 的个数。答案对 $K$ 取模。其中 $A$ 的长度 $M\le 20$,$N\le 10^9$,$K\le 1000$ 。题解矩阵乘法优化dp。用 $\text{f[i][j]}$ 表示在 $X$ 中做到第 $i$ 位,匹配到 $A$ 中第 $j$ 位的方案个数。最终的答案即为:$$\sum_{i=0}^{M-1} \text{f[...
access_time    bookmark 题解    comment 0 条评论
省选/NOI-
题意给出一张无向连通图,求 $S$ 到 $E$ 经过 $N$ 条边的最短路。其中边数 $T\le 100$ ,点的编号 $\le 1000$ ,$N\le 10^6$ 。题解因为是连通图,所以点最多有 $T+1\le 101$ 个。显然 $O(T^3)$ 的 $\text{Floyd}$ 是可以接受的。考虑 $\text{Floyd}$ 的过程:$$\text{dis[i][j]}=\min...
access_time    bookmark 题解    comment 0 条评论
提高+/省选-