复习用，仅记录我知道的方法，个人的见识很少，理解很浅。分类参考《dp 题方法总汇》。
生成结构
集合（背包）
无序。
- 以任意顺序转移，依次确定每个数的系数。
排列
有序，且性质优秀。
两种题：统计排列，统计映射（位置分配）。
排列即位置与值的二分图完美匹配：
- 将匹配拆为先后两部分，按权值依次一起处理左右部点，记录已匹配的对数：P14364 [CSP-S 2025] 员工招聘、CF285E Positions in Permutations。
- 按左部点/右部点（排列/逆排列）顺序依次添加匹配：
- 考虑已匹配的另一部点的相对顺序：
- 依左部点（位置）：AT_dp_t Permutation）。
- 依右部点（数值）：排列逆序对 DP、连续段 DP。
- 考虑另一部点的绝对大小（通常依赖单调性）：
- 依左部点：只填一个单调子序列，剩下的组合计数解决；又如 CF1437F Emotional Fishermen。
- 依右部点：构建笛卡尔树的区间 DP（分成子问题后右部点看相对顺序，归并修正贡献）。
- 考虑已匹配的另一部点的相对顺序：
序列
有序，比排列更复杂。
二分图视角：一个左部点恰匹配一个右部点，一个右部点可匹配多个左部点。
防止算重：
- 重排类问题，先对映射计数，再除以阶乘：AT_abc431_f [ABC431F] Almost Sorted 2。
- 对相同数值一起转移。
其他和排列类似。一些特殊序列的常用方法：
括号序列
栈、树等结构都可以视作括号序列。
- 从左到右填，记录未匹配的左括号数：CF1153F Serval and Bonus Problem。
- 状态表示 \((\ldots)\)，有拼接和围括号两种转移：2025.9.25 T4。
- 折线图。
字符串
可以视作自动机上的路径。
- 从前往后或从后往前一位位填，构建一个自动机状态记录关键信息：AT_agc046_d [AGC046D] Secret Passage。
数
统计范围：\([1,x]\) 中的所有数，\(x\) 在 \(y\) 进制下有 \(n\) 位。
本质是带“数的范围”限制的字符串，所以给自动机加状态即可。
- 从高位到低位填：记录是否顶上限、是否已有非 \(0\) 位。
- 从一段区间的两端扩展：先钦定匹配的是哪一段，