计数杂题笔记

详细的做法较少，偏向总结性的内容。

1. P3643 [APIO2016] 划艇

由于没有后效性，所以 $O (n a)$ 的暴力 DP 是容易的。

容易发现将 $a, b$ 离散化后，对区间做 DP 也是一样的。

但是发现 DP 不好转移，根本原因是相邻两个闭区间会相互影响。

于是向左闭右开区间转换，如 $[a, b], [b, c] \to [a, b), [b, b + 1), [b + 1, c + 1)$ 。

其实就是对原区间的右端点加一再丢进离散化里即可实现。

2. CF53E Dead Ends

educational's thing：钦定转移顺序可以避免重复计数，比如对于一个状压状态强制只能从最高位转移。

3. P2606 [ZJOI2010] 排列计数

NOIP 2024 T2，ljs 说是 dp，我说一个变量直接数就可以了。

事实上我的想法是愚蠢的，因为前者是一种通用的思考方式，可以优化到后者，我属于跳跃的歪打正着的思考方式。

比如这题，设 $f_{i}$ 表示大小为 $i$ 的树的方案数，因为除了根是最小值，剩下的数字放哪没有必然关联，不能用一条式子直接得出，需要 DP。

于是剩下的数选一些构成左子树，剩下的构成右子树即可，递归成子问题，转移是 $O (1)$ 的。

4. P3244 [HNOI2015] 落忆枫音

添加限制的题目，先思考减少限制，再思考加限制的影响。

没有加的那条边，很容易想到答案就是每个点都可以任选一条入边作为生成树的入边。

接着考虑加的那条边，其实就是要剔除选择的入边和新边恰好成环的情况，一次 DP 即可。

5. P5204 [USACO19JAN] Train Tracking 2 P

研究一下这些区间，发现有的区间是可以确定某些位置的，如 $min a_{[l, r]} < min a_{[l + 1, r + 1]}$ ，那么就可以确定 $a_{l}$ 是前者。

那么现在就被割成了若干个还没确定的区间，可以发现这些区间的每个滑动窗口的值是相等的。问题转换为：求长度为 $len$ 的序列，保证每相邻 $k$ 个数最小值为 $v$ ，的方案数。

于是直接 DP，设 $f_{i}$ 表示考虑前 $i$ 位的答案，每次直接转移， $f_{i} \leftarrow f_{i - 1} \times (max - v + 1)$ ，然后减去从 $i - k + 1 \sim i$ 一个 $v$ 都没选的情况，此时强制了 $i - k$ 选 $v$ ，所以要从 $f_{i - k - 1}$ 转移。

6. AT_arc058_c [ARC058E] 和風いろはちゃん

直接做显然会算重，并且重复的方式很诡异，思考了之后会发现容斥原理和二项式反演都行不通。

于是正难则反，考虑一个俳句都没出现的方案数。

于是考虑从前往后 DP，但是发现按照题意判定，还要存 $5 - 7 - 5$ 的分割点，状态数就炸了。

因此要思考更方便的判定方式，现在是分割点数太多，就尽量把判定往一个点靠，那么可以判断当前 $i$ 结尾的前缀和是否同时出现了 $Z, Y + Z, X + Y + Z$ ，出现了就是不合法。

由于 $X + Y + Z$ 很小，是否出现了这个和直接用状压即可，时间复杂度 $O (n \times 2^{X + Y + Z} \times 10)$ 。

7. AT_arc059_d [ARC059F] バイナリハック

一开始想的设 $f_{i, j}$ 表示匹配前 $i$ 个数按 $j$ 次键，转移就让 $i \to i + 1$ ， $j \to j + k$ 转移， $j$ 增加的部分可以用类似卡特兰数状物解决，但是思考了一会发现没有前途，只能 $O (n^{3})$ 。

于是打开题解就发现了：

可以按 $j \to j + 1$ 的增加来做，这样子 $i$ 的变化是 $O (1)$ 的。

所以说一个状态不一定是走错方向的，还要看转移选择的方向对不对。

8. AT_arc203_c [ARC203C] Destruction of Wall

首先转化成从 $(0, 0) \to (n, m)$ 方便处理。

$n + m < k$ 无解， $n + m = k$ 与 $n + m + 1 = k$ 是简单的。

接着是 $n + m + 2 = k$ ，此时任意多打穿两条路，然后发现在拐点处走出一个正方形的方案会被算重。

于是就想着枚举拐点，发现不可做。

实则可以直接把正方形看成一个整体，那就是要向右走 $n - 1$ 次，向下走 $m - 1$ 次，并挑两步之间插入一个正方形，这样是简单的。

最后还有一种走 S 形的情况，即返祖，同理把返祖的

  ---
  |
---

  |     |
  | --- |
  |     |

两个部分看成一个整体，那么针对第一种情况，就是要向右走 $a = n - 2$ 步，向下走 $b = m + 1$ 步，还有一个条件是插入这个结构时必须已经向下走过，如何解决？先不考虑这个限制求出方案数，即 $(\binom{a + b + 1}{a}) \times (b + 1)$ ，后面那个是选择结构放哪，然后强制把结构放到第一个向下走的前面，把结构视作向下走的求方案数即可。

计数杂题 笔记 ​

1. P3643 [APIO2016] 划艇 ​

2. CF53E Dead Ends ​

3. P2606 [ZJOI2010] 排列计数 ​

4. P3244 [HNOI2015] 落忆枫音 ​

5. P5204 [USACO19JAN] Train Tracking 2 P ​

6. AT_arc058_c [ARC058E] 和風いろはちゃん ​

7. AT_arc059_d [ARC059F] バイナリハック ​

8. AT_arc203_c [ARC203C] Destruction of Wall ​