A
一个字符串，你要选最多的区间出来，满足两两不交，且右边的区间必须是左边区间的严格子串。
\(n\le 5e5\).
注意到答案是 \(\sqrt n\) 级别的。
那么我们设计一个 dp，设 \(f_{i,j}\) 表示 \([j,j+i-1]\) 这个区间以及右边是否能选出 \(i\) 个。
转移只需要检查大区间减去左端点/右端点后的字符串是否存在。
可以用 Hash 来计算。只能通过 \(n\le 1e5\).
事实上我们可以设计另一种状态\(f_i\) 表示以 \(i\) 开头右边能选多少个区间。
考虑二分答案 \(mid\)，检验 \(f_j\ge j-1\) 且 (\(lcp(i,j)\ge mid-1\) 或 \(lcp(i+1,j)\ge mid-1\)).
然而我们可以用 SA，转化为 \(rk_j\) 在某区间内，\(j\in [i+mid,n]\) 的最大值。
B
一张无向图（\(n\le 16,m\le n(n-1)/2\)），你需要把每条边重定向，使得从 \(1\) 出发的能到的点集和从 \(2\) 出发的能到的点集有交集。
求方案数取模 \(1e9+7\).
考虑用总方案数减去不合法方案数。
设 \(1\) 能到的点集 \(s1\)，该点集里的边的方案数为 \(f_{1,s1}\)，\(2\) 同理。
\(s1,s2\) 向外的边必须定向到自身。不在 \(s1,s2\) 的边可以任选。
设一个点集边内部的总数为 \(E(S)\)。不合法方案数是 \(\sum _{s1,s2} f_{1,s1}\times f_{2,s2}\times 2^{E(V-s1-s2)}\).
设我们求 \(f_{x,S}\)，还是总方案数减去不合法方案数。
不合法的是：设从 \(x\) 出发仅能到达 \(T\)，\(T\) 向外的边必须定向到自身，其他边可以任选。
那么其贡献 \(f_{x,T}\times 2^{E(S-T)}\).枚举子集即可。
C
有 \(n\) 个点，每个点有黑白两种颜色，有些点没被确定颜色。
边是有向边，只能从小的点通向大的点，且两点颜色相反。
问所有合法路径数是奇数的图多少个。