A
首先特判四个角是空的，或者第一三行有连续两个空的。
然后，标算做法好像是按照第二行的连续段划分之后做一个比较难讨论的 DP。
但是我们注意到，每个第二行的空位，要么是上下都早于它，要么是左右都早于它，然后可以减掉上下左右都早于它的，且这些边永远构成树形图森林，因此我们容斥成内向树森林的拓扑序计数即可。
时间复杂度 \(O(N^2)\)。
B
考虑钦定一棵笛卡尔树，可以用区间 DP 刻画。注意到我们不需要保证这棵笛卡尔树保证每个点都是子树的最大值。
然后每个位置预处理一个凸包，转移可以做到 \(O(N^3 \log K)\) 或者 \(O(N^3 + N \sum K)\)。
C
按照 DP 值大小顺序计算，精细实现可以做到 \(O(n^3/w)\)。
D
按照值顺序插入边，每一次把一类边一并插入，大力 DP 就是 \(O(n^4 k^3)\) 的，插值掉一维会变成 \(O(n^3 k^2)\)。
E
首先求出最短路，记 \(i\) 到 \(b+1\) 和从 \(b+1\) 出发的最短路之和 \(w_i\)，问题转化为将 \(\{1, \dots, b\}\) 划分为 \(S_1, S_2, \dots, S_s\)，最小化 \(\sum_j (|S_j|-1) \sum_{i \in S_j} w_i\)。
显然如果确定了 \(|S_j|\)，那肯定是把最大的 \(w_i\) 分给最小的 \(S_j\)。我们据此暴力 DP 可以做到 \(O(n^2 \log n)\) 而且常数很小（任意时刻集合数量乘最小的集合大小要小于等于点数）。
当然也可以忽略一些性质用 WQS 二分和二分栈做到 \(O(n^2 \log n)\) 或 \(O(n^2 \log V)\)，或 \(O(n\log n\log V)\) 等复杂度。
F
相当于对于 \(i=1,\dots, n\) 确定了一个随机种子 \(x\) xorshift \(i\) 次之后模 \(i\) 的余数。
考虑每个时刻，当前 xorshift 结果的每一位都是初始时 \(x\) 某一些位的线性组合，因此我们至少可以从每个 \(i\) 读出 \(\nu_2(i)\) 个方程。
由于 xorshift 伪随机效果非常好，因此矩阵的秩很大，只需要暴力枚举自由元的取值即可。
G
从题意里可以读出一些限制：每一位有一些字母不能选，每一种字母要么是限制了出现次数恰好是某个数，要么是限制了出现次数至少是某个数。
暴力一个个字符加入是 \(O(|\Sigma|3^k)\)，改成子集卷积可以做到 \(O(|\Sigma|k^2 2^k)\)，但其实我们在每一层再做一个从左往右的 DP 就可以做到同复杂度。进一步，注意到记录出现次数的那一维只需要保留到下界，而下界之和不超过 \(k\)，因此变成了 \(O(|\Sigma|k2^k)\)。
据说直接从左往右选字符也可以压到 \(O(|\Sigma|k2^k)\) 甚至 \(O(k^2 2^k)\)？而且这个做法应该更不满一点。
H
可以证明所有 LCA 在一条祖先后代链上，否则可以找到一个分界点使得其不满足条件。
然后直接 DP 就可以了，时间复杂度 \(O(n^4)\)。
I
众所周知正确的做法是按右端点从小到大选。记真做法选中的是红区间，假做法选中的是蓝区间，同时被选的是紫区间。
那么考虑一组染色方案确实是算法选出来的染色当且仅当：
相邻两个红区间之间没有完整的未染色区间。
相邻两个蓝区间之间没有未染色区间的左端点。
第 \(i\) 个红区间的右端点不大于第 \(i\) 个蓝区间的右端点，且大于第 \(i-1\) 个蓝区间的右端点。
考虑从后往前插入区间，每次我们插入一对红蓝区间的右端点而先不考虑其左端点，同时顺带插入右边一对红蓝区间的左端点，且要记录是否是紫区间，画一画图就可以转移了。
从前往后插入可能也存在某种方式是可做的。
时间复杂度 \(O(n^2)\)。不过它其实可以是半在线卷积，可以做到 \(O(n\log^2 n)\)。
J
有一个显然的 \(O(n^3)\) 的 DP，但是没啥救。
考虑改成 \(f(i, j, k)\) \((0 \le j \le 1)\) 表示钦定 \(\max(x_{i-1}, x_i) = x_{i-j} = k\)，且仅确定了 \(x_1, \dots, x_{i-j}\) 的值。转移的时候再确定中间的值，可以前缀和优化，时间复杂度 \(O(n^2)\)。
K
考虑这六条边构成的子图，只有 \(9\) 种本质不同的，而且可以使用 bitset \(O(n^3/w)\) 求出（我猜在稀疏图上也可以 \(O(m\sqrt m)\)）。
L
把答案转化为 \((\sum_{S \subseteq V} 2^{C(S)} \bmod 4)/2\)，其中 \(C(S)\) 是 \(S\) 的导出子图的连通分量个数，其具有组合意义：黑白染色使得每条边两侧颜色相同，直接状压即可 \(O(n 3^k)\)，其中 \(k=\max |a_i-b_i|\)。
M
这个模型应用串并联图方法会有点麻烦，但是不妨直接取出 \(\ge 3\) 度点，每取出一个就把它相邻的边删掉，最多会取出 \(m/3\) 个。暴力枚举它们的选取情况，剩下的部分差不多是链和环的独立集计数，不过还要特判三元环。时间复杂度 \(O(n 2^{m/3})\)。
X
考虑我们总是可以钦定每次匹配的都是连续一段，因此把这些钦定好的合法子串删掉之后只会剩下形如 \(\texttt{))}\dots\texttt{)(}\dots\texttt{((}\) 的串。
因此答案是
\[ \sum_{2m\le n} m \cdot \frac{1-x^{n-2m+1}}{1-x} \cdot [t^m] (1+C(xt))^{n-2m+1} \]
其中 Catalan 数 \(C(x)\) 满足 \(C(x) = x(1+C(x))^2\)。
右边的东西显然可以表为一个预处理阶乘后可以 \(O(1)\) 计算的结果，因此就 \(O(n)\) 解决了此题。