图论这一块内容比较多，而且题目涉及的 Trick 也很多，因此分若干篇。 本文略去所有算法本身性质的证明过程。 最短路 Dijkstra和SPFA $\text{Dijkstra}$ 算法基于一个重要的性质：全局最小值不可能再被任何边更新。这样，在边权为非负数的最短路问题中显然满足，在存在负边时不满足。同时，保证了最多从每个节点处扩展 $1$ 次，…

计数杂题。 CF840C On the Bench 先进行一些基本的观察。 $\texttt{Observation}$ ${a_i}$ 中乘积为完全平方数的数集，一定是相对封闭的。因此我们可以将 ${a_i}$ 划分成若干个集合，满足其中两两乘积为完全平方数。 $\texttt{proof}$ 考虑和 $a_i$ 相乘为完全平方数的数集 ${a_…

Trie luogu2922 [USACO08DEC]Secret Message G 给定两个字符串序列 $a$ 与 $b$，对于 $b$ 中每个字符串 $t$，求 $a$ 中有多少个字符串 $s$，满足以下两个条件之一 $s$ 是 $t$ 的前缀。 $t$ 是 $s$ 的前缀。 两个字符串序列中所有字符串长度之和不超过 $500000$。 把 …

作为一道生成函数的练习题。 不用生成函数推了好久还是错的。 以后遇到这类递推关系绝对首选 GF（能力范围内） 简单观察不难发现，如果 $m<n$，那么无解。如果 $m=n$，那么只能是连续的 $n$ 个01。 考虑 $m>n$ 的情况，不难发现任何一个合法串都可以在一个初始串——连续的 $n$ 个01中插入 $m-n$ 个 $0$ 得到…