P4022 [CTSC2012] 熟悉的文章
考虑答案的可二分性，如果 \(L\) 可行 那么 \(L_0 \leq L\) 一定也可行（题目条件），如果 \(L\) 不可行，若存在 \(L_1 \geq L\) 可行，那么矛盾。故有可二分性。
考虑对于二分的答案进行 $\text {DP} $ ，考虑设 \(\text{dp[i]}\) 表示前 \(i\) 个字符的最大匹配长度，则有当前字符不匹配和匹配到一段连续的选择。
其中 \(s[j...i]\) 要能够匹配且匹配的长度 \(\geq L\)。
建立广义 \(SAM\)，此时发现转移的区间就是考虑每个位置 \(i\) 所能匹配的最长的长度 \(len_i\) 以及 \(L\) 的限制。
如果此时用线段树优化则复杂度为 \(O(n\log ^2 n)\)，无法通过 \(10^6\) 数据。
考虑此时 二分 \(+\) 线段树的形式，线段树的 \(\log n\) 往往能去除。
$ {\color{Red} 此时往往考虑单调性来优化dp} $
注意到 \(i - len_i\) 在 \(i\) 增加1的同时 \(len_i\) 最多也只会增加 \(1\)，即这个式子的值也就是左侧限制单调递增，此时用单调队列优化 \(dp\)。复杂度 \(O(n\log n)\)
P2565 [SCOI2009] 骰子的学问
构造题，存在特殊情况，只要通过样例就可以构造这种特殊情况。
CF662C Binary Table
考虑对于每一个行是否翻转的 \(2^n\) 种状态计算答案。对于某一列来说，其答案为 \(val \oplus s\) 自身与翻转后的 \(popcount\) 最小值。
$ {\color{Red} 对于情况一样的列开桶统计，这样的题目不是一行一行转移。}$
其中 \(cnt[i]=\min(popcount(i),popcount(i \oplus S))\) \(S= 2^n -1\)
#2340. 「WC2018」州区划分
考虑本题的判定条件实际上就是欧拉回路的判定条件，判断是否联通且是否\(deg\)均为偶数即可。考虑状压\(dp\)，设 \(dp[s]\) 表示当前选定城市的状态为 \(s\) 时的所有方案的总和。容易发现这是一个子集卷积的形式。
\(g[j]\)表示此时联通块的分子上的权值，而每次做完一子集卷积后把分母上的贡献除掉。由于要做 \(n\) 次子集卷积，复杂度 \(O(n^3 2^n)\)，无法通过、
$ {\color{Red} 其实子集卷积自身便带有一种阶段性，如果按照 \text{popcount}的大小从小到大做就行}$
具体的，在 \(popcount=i\) 时用前面的值两两做 \(FWT\) 后加到当前行，之后统一进行 \(IFWT\)。同时按照子集卷积的原理，将 $popcount = i $ 的位置上的值保留，其余的全部赋值成 \(0\) 。
$ {\color{Red} \text{Warning：}这一步必须在进行了 IFWT 之后再做。}$
CF150E Freezing with Style
套路题，直接二分之后点分治判断即可，和 [WC2010] 重建计划 一模一样。
P5495 Dirichlet 前缀和
感觉很有趣，实际上是对所有质数因子做了高位前缀和，同时也能做高位后缀和，在一些数论题的预处理中可以将 \(O(n\log n)\) 优化为 \(O(n\log\log n)\)，后者接近常数。这里的预处理指的是
\(F[i] = \sum_{i\mid j} G[j]\) 的形式，\(G[j]\) 往往是可以线性预处理的数论函数。