A
P9195 [JOI Open 2016] JOIRIS
逆天构造。直接看题解吧，主要是将列进行 k 染色，然后瞎 jb 做一下。
B
CF461E Appleman and a Game
我们可以先建出 SAM，设 \(dp_{i,u}\) 表示当前处理到 \(i\) 位，SAM 上到 \(u\) 节点当前最小答案。
由于答案具有单调性，考虑二分答案，也就是二分 \(mid\)，考虑如何检验最短的串是否不超过 \(\le n\)。
考虑把 SAM 修改一下，若某点不存在 \(c\) 的出边就将其连向根到 \(c\) 的节点。
现在问题转化为：给你一张有向图（即修改完的 SAM），满足上面有 \(4\) 个特殊点。
你从根开始走，每经过一条边则 \(cnt_1\) 加一，每到达一个特殊点则 \(cnt_2\) 加一。
当 \(cnt_2\) 为 \(mid\) 时过程终止。 你可以任意安排你走的路径，需要求出终止时 \(cnt_1\) 的最小值。
那么我们可以 dp，设 \(dp_{i,c}\) 表示当前走了 \(cnt_2=i\)，走到了第 \(c\) 个特殊点的最小答案。
考虑最短路求出特殊点之间的最小的 \(cnt_2\)。最后 dp 明显可以用矩阵快速幂优化。非常好一个题。
之所以想到可以二分答案是因为“最小值最大”；还有随着 \(n\) 增大答案不降，所以答案增大，\(n\) 也不降。
可以二分转倍增优化复杂度。
C
给出一个有向图，\(A\) 为其邻接矩阵，问 \(A\) 的周期以及第一个出现相同的位置。
乘法定义为与，加法定义为或。\(n\le 1e5\)，只有 \(n\le 200\) 才用输出第一个相同的位置。
缩强连通分量，一个强连通分量是其所有环大小的 \(\gcd\)，所有环的答案是 \(lcm\)。
对于求强连通分量的环可以考虑直接 dfs 一遍，对于所有返祖边算一下深度之差 +1 即为环大小。
求第一个相同的位置考虑倍增判定，先预处理矩阵的多少次幂。