比赛补题
ABC 350
C 题最开始因为一个变量在操作间不经意被修改吃了一发罚时，后怀疑自己方法有误，联想到了之前做过的一道排序题，敲完之后上交发现还是 WA 了。回到最开始的代码，检查了一下，发现了错误。虽然题目过了，但还是浪费了很多时间。或许不应该对自己的方法过早产生质疑。
F 题是一个非常经典的递归题（括号序列），这道题预计时间只有 30 min，却做了 60min 还没有做出来，剩下的题也没有时间开了。做这道题是只想到了常见的递归思路，并没有想到可以使用栈预处理每个区间的大小。
这次对 E 题的难度评估也出了问题，初次看到 E 以为是自己非常不熟悉的概率论，果断跳过，赛后看题解才发现是一道记忆化搜索配上了一点数学。没有想到预期成本其实就是成本的平均数。
杂题选做
定义一个集合 $S$ ，其中包含了所有的妹子，令 $F(S)$ 代表 $S$ 和前 $|S|$ 个男生匹配的结果，若 $S = \empty$ ，易得 $D(S) = 1$ 。因为 $n$ 的范围非常小，考虑直接进行枚举 $S$ 来求得答案。
状态转移方程 $D(S) = \sum_{x \in S} D(S – x)$ 。
时间复杂度 $O(n2^n)$ 。
通过二进制状态压缩是枚举一个人选不选的常用思路。
AC code
定义 $F(i, j)$ 序列 $1$ 到 $i$ 以第 $j$ 大为结尾的方案数，显然 $F(1, 1) = 1$。
对于 $j < i$ 如果 $S_{i – 2} =$ > ，则有 $F(i, j) = \sum_{j < k \le i} D(i – 1, k – 1)$ ，这是由于 $[1, i )$ 全排列和 $[1, j – 1]\cup[j + 1, i]$ 是等价的，~~这不废话？~~
如果 $S_{i – 2} = $< ，直接令 $D(i, j ) = \sum_{1 \le k \le j}D(i – 1, k)$ 。
~~这种题每次都挺玄学的？？？每次都是想一半，~~这也更加说明了动态规划基本上是含一个索引，接着是会影响下一次选择的状态。
AC code
定义 $F(i)$ 代表将 $i$ 强制染色，以 $i$ 为根的子树的方案数，$D(i)$ 代表子树外的方案数，最终答案为 $D(i) \times F(i)$。
经过简单推理可得：
$$F(x) = \prod F(to)+1$$
其中 $to$ 为 $x$ 的子节点。$F(to)$ 是子节点 $to$ 染成黑色的方案数，而 $+1$ 是将 $to$ 染成白色的方案数。
但是 $D$ 的推理就有一些麻烦了，公式如下：
$$D(x) = (D(fa) \times \prod F(v) + 1) + 1$$
其中 $fa$ 为 $x$ 的父节点，而 $v$ 为 $x$ 的兄弟节点。后面的 $+1$ 是将 $fa$ 染成白色的方案数，而 $F(v)+1$ 是将兄弟节点染成黑色和白色的方案数总和，将其乘上 $D(fa)$ 也就是指，将 $fa$ 染成黑色的方案数。
很显然，如果每次枚举都要计算一次 $\prod F(x) + 1$ ，时间复杂度是 $O(n ^ 2)$ 的，由于 $F(x) + 1$ 的值是恒定且不变的，此时有理由想到使用前缀后缀和优化。
此时的时间复杂度为 $O(n)$。
正难则反，若 $H \times W$ 的网格中没有障碍物，那么从 $(1, 1)$ 走到 $(H, W)$ 的方案数为 $\binom{H + W – 2}{H – 1}$ 。这是因为每次我们都可以做决策是向右还是向下，若我们选择了 $H – 1$ 次向下走（向右），那其余的选择一定能够确定。
为了方便表示，定义 $A(x1, y1, x2, y2) = \binom{x2 – x1 + y2 – y1}{x2 – x1}$。
考虑如何求 $(x1, y1)$ 到 $(x2, y2)$ 的方案数。若他们中间并没有障碍物，则方案数为 $A(x1, y1, x2, y2)$，若他们中间有一个障碍物 $(x0, y0)$，从 $(x1, y1)$ 到 $(x0, y0)$， 的方案数为 $A(x1, y1, x0, y0)$，从 $(x0, y0)$ 到 $(x2, y2)$ 的方案数为 $A(x0, y0, x2, y2)$，而从 $(x1, y1)$ 在经过 $(x0, y0)$ 的情况下，到达 $(x2, y2)$ 的方案数为 $A(x1, y1, x0, y0) \times A(x0, y0, x2, y2) $，用总方案数减去经过 $(x0, y0)$ 的方案数即是题目所求的内容。
定义 $D(i)$ 为：从 $(1, 1)$ 不经过其他障碍物达到第 $i$ 个障碍物的方案数，若我们把点 $(H, W)$ 当作第 $n + 1$ 个障碍物，则最终的答案为 $D(n + 1)$。我们将所有障碍物按照坐标递增排序，当我们计算到第 $i$ 个障碍物时，$D(i) = A(1, 1, xi, yi) – \sum_{j = 1}^{j < i} D(j) \times A(xj, yj, xi, yi)$ 。
AC code