题面 传送门：SPOJ 694 Solution 这题可以用SAM来搞，也可以用SA来搞。但无论是哪种搞法，都是基本操作。下面我们来分别讲解一下怎么搞。 SAM 这题用SAM来求就十分粗暴简单。不会SAM的小伙伴可以戳这里 首先，我们先把SAM建出来。根据SAM的性质，我们从出发点随着SAM任意走，走到哪里都是一个完全不同的子串。因此，我们只需要对SAM做一个拓扑序DP/记忆化搜索即可求出SAM上的路径总数，既不同子串的数量。 SA 这题我们显然还是要把后缀数组和height建出来的，不会SA的小伙伴可以戳这里 我…

题面 蒟蒻博客：QAQ Solution 这是一道神题 首先，我们不妨想一下K=0，即求最短路方案数的部分分。 我们很容易可以想到一个做法，就是魔改迪杰斯特拉做法： 一个点可以更新到达其他点的距离，那个点的方案数就是这个点的方案数；如果一个点所更新出来的距离和之前的相等，那个点的方案数加等当前点的方案数。 用式子可以表现为： $$f[i]=f[i] (dis[j]>dis[i]+x)$$ $$f[j]+=f[i] (dis[j]==dis[i]+x)$$ (i表示当前点，j表示它更新的点，x为i到j那条路的距离) …

题面 传送门:洛咕 Solution 挺有意思的一道题。 题面已经挺明显的描述出了这题的主要思想：倍增。 先这样想，我们可以把这题这样建模：有一堆点，若两个点之间的距离之和可以达到2的n次方，那么这两个点可以用1的时间相互到达。 也就是说，我们把距离能为2的n次方的点对用边权为1的边连上，再做一次最短路径，就可以求出答案了。 接下来问题就是如何求出每两个点是否能以2的n次方的时间相互到达。 考虑使用DP。 我们设$f[i][j][k]$ 表示 $i$到$j$是否能以$2$的$k$次方的距离相互到达。 转移的时候得运…

题面 传送门：洛谷 Solution 这题显然要先把缩点做了。 然后我们就可以考虑如何处理走反向边的问题。 像我这样的蒟蒻，当然是使用搜索，带记忆化的那种（滑稽）。 考虑设$f(i,j)$表示到达第i个点，还能走j次反向边，所能到达的最多的点的数量。 转移可以表示为： 如果x能到达1所在的强连通分量或max出来的值不为0，说明当前状态可行，否则不可行。 然后用记忆化搜索表达出来就OK了 Code #include<iostream> #include<cstdio> #include<…