₯ 特训
wxr_
·
·
个人记录
https://www.luogu.com.cn/training/641872 和 「CodeChef」Mex Subsequence。
看似 DP 特训，实则 DS 特训。
优先考察性质，否则后果参考 S-T3。
技巧一
以 「CEOI2016」kangaroo 为例。
价值两个脆香米的好题。
考虑将 1 \sim n 这 n 个数按顺序从小到大插入，这样已在序列中的都比当前数小，将要插入序列中的都比当前数大。
发现转移时就只与当前的连续段个数相关。
而为了保证方案合法，还需要使得每个连续段都是形如 M 形，才能保证之后加入的可以新开连续段或合并两段。
可以线性。
CF704B。
AT_arc146_e。
插入 DP 插的不一定是排列。
技巧二
以 「POI2013」LUK-Triumphal arch 为例。
神秘博弈论。
这种选点的好像都要二分。
技巧三
以 「CEOI2017」Chase 为例。
提到树上路径相关问题的两种思考方式：枚举 LCA 和枚举端点。
还有一个是点分治。
寄巧四
以 「CF1476F」Lanterns 为例。
3000 题当然有 3000 的做法。
考察打开 [1, i] 的灯笼后，照亮的区域是 [1, i] 中的某些点和 [i + 1, n] 的一段前缀。而 [i + 1, n] 的灯笼打开后在 [1, i] 中照亮的是一段后缀。
因此设 f_{i, j} 表示打开 [1, i] 的灯笼后在保证 [1, j] 的区域被照亮的情况下最远可以照到的范围是 [i + 1, f_{i, j}]，若不能保证 [1, j] 被照亮则为 -\infin。
不难发现当 i 一定时，f_{i, j} 随 j 的增大而减小。
转移时，如果第 i 个灯笼向右，那么转移为：
$f_{i, i} \gets \max(f_{i - 1, i - 1}, i + p_i)(f_{i - 1, i - 1} \ge i)$。
因为只有当可以将 $[1, i - 1]$ 覆盖完时第 $i$ 个灯笼才可能向左，所以有：
$f_{i, j} \gets f_{i, i - 1} \gets f_{i - 1, i - p_i - 1}(f_{i - 1, i - p_i - 1} > -\infin)$，
$f_{i, i} \gets f_{i - 1, i - p_i - 1}(f_{i - 1,i - p_i - 1} \ge i)$。
具体实现上用线段树维护 $f$，每次修改的都是一段区间。
虽然这个做法确实是依托，但是确实体现了常规 DP 的一种思路：
1. 阶段：将问题划分为若干阶段，阶段间存在一定顺序。
2. 状态：当前阶段中会对后续决策产生影响的信息。
3. 转移
4. 优化：优化状态和数据结构优化转移。两者本质是一样的，
## 技巧五
以 [「CF1152F2」Neko Rules the Catniverse (Large Version)](https://codeforces.com/problemset/problem/1152/F2) 为例。
插入 DP。依然是插入的同时保证一定的大小关系。
注意到 $m$ 和 $k$ 都很小，所以可以设进状态里。
再注意到转移不变且 $n$ 很大，所以进行一个矩阵的快速幂。
## 技巧六
https://www.cnblogs.com/alex-wei/p/Dirichlet.html
---
以 [「BZOJ4665」小 w 的喜糖](https://www.luogu.com.cn/problem/P10597) 为例。
容斥。
抛开题目不谈，先证一遍二项式繁衍。
> 你知道为什么容斥系数是 -1、1、-1、1 吗？
>
> —— [Just_int_mian](https://www.luogu.com.cn/user/818593)
首先，有二项式定理 $(a + b)^n = \sum\limits_{i = 0}^n \dbinom{n}{i} a^i b^{n - i}$。
然后，取 $a = -1, b = 1$，得 $\sum\limits_{i = 0}^n (-1)^i \dbinom{n}{i} = [n = 0]$。
设 $g_n = \sum\limits_{i = 0}^n (-1)^i \dbinom{n}{i} f_i$。
则有
$$
\begin{aligned}
& \sum\limits_{i = 0}^n (-1)^i \dbinom{n}{i} g_i \\
= & \sum\limits_{i = 0}^n (-1)^i \dbinom{n}{i} \sum\limits_{j = 0}^i (-1)^j \dbinom{i}{j} f_j \\
= & \sum\limits_{i = 0}^n \sum\limits_{j = 0}^i (-1)^i (-1)^j \dbinom{n}{i} \dbinom{i}{j} f_j \\
= & \sum\limits_{i = 0}^n \sum\limits_{j = 0}^i (-1)^{i - j} \dbinom{n}{j} \dbinom{n - j}{i - j} f_j \\
= & \sum\limits_{j = 0}^n \dbinom{n}{j} f_j \sum\limits_{i = j}^n (-1)^{i - j} \dbinom{n - j}{i - j} \\
= & \sum\limits_{j = 0}^n \dbinom{n}{j} f_j \sum\limits_{i = 0}^{n - j} (-1)^{i} \dbinom{n - j}{i} \\
= & \sum\limits_{j = 0}^n \dbinom{n}{j} f_j (1 + (-1)) ^ {n - j} \\
= & \sum\limits_{j = 0}^n \dbinom{n}{j} f_j [n = j] \\
= & f_n \\
\end{aligned}
$$
所以 $f_n = \sum\limits_{i = 0}^n (-1)^i \dbinom{n}{i} g_i \iff g_n = \sum\limits_{i = 0}^n (-1)^i \dbinom{n}{i} f_i$。
然后把 $g_i$ 乘 $(-1) ^ i$，得到 $f_n = \sum\limits_{i = 0}^n \dbinom{n}{i} g_i \iff g_n = \sum\limits_{i = 0}^n (-1)^{n - i} \dbinom{n}{i} f_i$。
组合意义是对于**一个**大小为 $n$ 的集合 $S$，$F(S) = \sum\limits_{T \subseteq S} G(T)$，而 $G(T)$ 只与 $\vert T \vert$ 相关，就有 $f_n = \sum\limits_{i = 0}^n \dbinom{n}{i} g_i$。也叫子集反演。
然后把下标反着写，得到 $f_i = \sum\limits_{j = i}^n \dbinom{j}{i} g_j \iff g_i = \sum\limits_{j = i}^n (-1) ^ {j - i} \dbinom{j}{i} f_j$。
组合意义是 $g_i$ 表示**所有**恰好选 $i$ 个的方案数，$f_i$ 表示钦定了 $i$ 个必选后剩下的 $n - i$ 个中任选的方案数，这样每个 $g_j$ 中的方案就会在 $f_i$ 中被统计 $\dbinom{j}{i}$ 次。也叫超集反演。
至于为什么要反演，一般是因为有的数据自然地契合某种统计方式。
## 总结总结
~~因为万物起源 DP，所以 DP 并没有什么共同点，没什么好总结的。~~
~~因为 DP 只是一种工具，所以更应该注重思维的提升，没什么好总结的。~~