ABC213
E
不难转化为经典的 0-1 bfs。
AC Submission
F
考虑 SA。
建出后缀数组后，令 \(h_i=LCP(suf_{sa_i},suf_{sa_{i-1}})\)，根据经典结论有 $$LCP(suf_{sa_i},suf_{sa_{j}})=min_{i<k\leq j} h_k$$
问题转化为给定一个数组，求以 \(i\) 为左/右端点的区间 min 之和。
使用单调栈不难做到 \(O(n)\) 递推。
总复杂度 \(O(n \log n)\)，瓶颈在 SA。
AC Submission
G
设 \(f_S\) 表示点集为 \(S\) 的联通子图的个数，\(g_S\) 表示点集为 \(S\) 的子图的个数。
记点 \(k\) 的答案为 \(ans_k\)，\(U\) 为点的全集。
由于要求 \(1,k\) 联通，考虑钦定 \(1,k\) 所在连通块，有：
\[ans_k=\sum_{ \left \{ 1,k \right \} \subset S \subset U} f_S \times g_{U\setminus S}
\]
\(g_S\) 是好计算的，为 2 的边数次方。
考虑如何计算 \(f_S\)，一个简单的想法是正难则反一下，转变为计数不连通子图的个数。
同样的，我们钦定一个点 \(u \in S\) 及其所在的连通块，并钦定其和此连通块以外的点均不连通，有：
\[f_S=g_S-\sum_{u \in T \subseteq S} f_T \times g_{S\setminus T}
\]
实现中取 \(u=\operatorname{lowbit}(S)\) 即可，瓶颈在枚举子集，复杂度 \(O(3^n)\)。
AC Submission