目录
- P4463 [集训队互测 2012] calc（拉插优化 dp）
- P4484 [BJWC2018] 最长上升子序列（状压 dp）
- ARC138E - Decreasing Subsequence（构造双射）
- P5400 [CTS2019] 随机立方体（二项式反演）
- AGC064D - Red and Blue Chips（构造充要条件）
- CF1942G. Bessie and Cards（反射容斥）
- CF1874F. Jellyfish and OEIS（容斥、构造双射）
- P8478 「GLR-R3」清明（乘法分配律）
- P4931 [MtOI2018] 情侣？给我烧了！(加强版)（错排）
- qoj 5357. 芒果冰加了空气（刻画）
- P10104 [GDKOI2023 提高组] 异或图（数位 dp、容斥）
- Baekjoon 23510 Wise man（数位 dp）
- （skipped）P5417 [CTSC2016] 萨菲克斯·阿瑞
- CF1456E XOR-ranges（数位 dp、独立性）
- （skipped）CF1081G Mergesort Strikes Back
- 以下的题目等待更新
- CF1707D Partial Virtual Tree
- CF1647F. Madoka and Laziness
- CF1349F1 Slime and Sequences (Easy Version)
- P5359 [SDOI2019] 染色
- P5320 [BJOI2019]勘破神机
P4463 [集训队互测 2012] calc（拉插优化 dp）
先简单地写一个二维的 dp 方程。然后发现因为所涉及的操作只有平移、前缀和、点乘一次函数的操作，我们将 dp 的某一行看成一个代数式 \(f(x)\)，使得这行的第 \(x\) 个数刚好是 \(f(x)\)（注意不是第 \(x\) 项系数），然后我们就能直接证明 \(f(x)\) 是多项式！然后拉格朗日插值即可。
P4484 [BJWC2018] 最长上升子序列（状压 dp）
有两种求 LIS 的方法，应该选哪一种？如果选择 \(O(n\log n)\) 的方法，则无法在 \(\widetilde{O}(2^n)\) 的状态内同步记下选过哪些数，会较为失败。使用 \(O(n^2)\) 的方法，如果我们从排列出发，从左往右扫排列的第 \(i\) 个数，我们也需要记下选过哪些数，还要记下整个 dp 数组。
发现瓶颈其实在于要记下选过的数，这个东西记完之后就没有什么额外空间进行操作了。所以我们改从值域考虑这个问题，也有两个角度，第一种是从左往右扫，每次从值域中间、序列末尾插入；第二种是从下往上扫，每次从值域末尾、序列中间插入。做到这里两个角度已经没有什么区别，你对 dp 数组取前缀 max 再差分就会发现其值域变为 \(\{0, 1\}\)，就可以存储了。然后再简单地计算一下复杂度就是 \(O(n2^n)\)，接下来的事情就是打表了。
ARC138E - Decreasing Subsequence（构造双射）
当你终于将题目读对的时候会发现这个限制相当自由，如果只是从阶梯的形状下手会极为失败。对此，由题解知，我们将 \(i\) 向 \(a_i-1\) 连边，这样每个点要么连 \(-1\)（就是抛弃掉它）要么连向 \([0, i)\) 的其中一个点，每个点的入度和出度都为 \(1\)，形成若干条链。最后就是发现下降子序列的形状是 \(k\) 条层层包含的边，枚举这个变所在的链，可以从那 \(k\) 条边中间将 \(k\) 条链拆开。然后使用第二类斯特林数（斯特林子集数）对左右两边的点进行划分链。注意这个映射构造的时候多了一个 \(0\) 号点，是原来的问题中不存在的。
P5400 [CTS2019] 随机立方体（二项式反演）
可能的第一个想法是：立方体中的最大值是极大点，将其提取出并删除它所在的三个方向的平面。然后选择下一个极大点，就会发现刚才删去的东西会对下一个有一点影响。那么我们应该从小到大枚举极大点吗？有可能，可以尝试一下，发现这样做就舒服很多。后面的事情就是，把题改成方案数，然后写出式子，消去若干阶乘。最后只需要惊讶地发现刚才做的事情只能保证有至少 \(k\) 个极大点（或者说“钦定”了 \(k\) 个极大点），于是快速地默写二项式反演的式子即可通过。
\[g(k)=\sum_{k\leq i\leq n}\binom{i}{k}f(i)\Leftrightarrow f(k)=\sum_{k\leq i\leq n}(-1)^{i-k}\binom{i}{k}g(i) \]AGC064D - Red and Blue Chips（构造充要条件）
计数多少个本质不同的答案序列，太难了！有一个较为通用的套路是考虑怎么判定答案是否可以被构造。
写一下这题的过程，你从右往左扫描原串，扫到 \(R\) 就要有一个靠前的 \(R\) 脱落，扫到 \(B\) 就要大概是一个 \(B\) 带着它前面的东西脱落。有将 \(B\) 脱落这个过程，我们再重写一下，现在有若干个 \(B\) 结尾的串和需要单独分离的答案串的极长 \(R\) 前缀，扫到 \(R\) 就要有一个串的第一个 \(R\) 脱落，扫到 \(B\) 就要有一个 \(B\) 结尾的串分裂成两个 \(B\) 结尾的串，最后问是不是每个原串 \(R\) 都能找到脱落的答案串。那就很好办了，发现将 \(B\) 结尾的串分裂时，会多出来一个 \(R\) 的极长连续段可以进行脱落，而且是任意一个段都能脱落出来，那我肯定是贪心地选最长的那一个。
现在问题就变成了：在原串上从右到左统计每个 \(B\) 前面的 \(R\) 极长连续段长度记作 \(a\)，在答案串从左到右统计每个 \(B\) 前面的 \(R\) 极长连续段长度记作 \(b\)，然后排序 \(b[2\cdots len(b)]\)，并要求 \(len(a)=len(b)\)，\(a\) 做前缀和后的数组对应位都小于等于 \(b\) 做前缀和后的数组。可以直接 dp。
CF1942G. Bessie and Cards（反射容斥）
可能是转格路计数后做反射容斥，而事实就是这样，因为确定起点、终点、长度后，走过的 \(+1\) 和 \(-1\) 的步数是完全确定的，不会随着什么东西的变化而变化。所以就直接做，首先将抽 \(k\) 次改为 \(+k-1\) 牌，删掉 \(+0\) 牌，枚举抽了几张牌之后停止，或者没有停止过，那么所用的 \(+1\) 牌和 \(-1\) 牌的数量是完全确定的，什么都不用担心了。
CF1874F. Jellyfish and OEIS（容斥、构造双射）
上来就容斥，枚举一个区间的集合表示这些区间满足题目那个鬼限制。然后可以发现，两个有交的区间（\(l_1<l_2<r_1<r_2\)），可以通过额外加一个它们的交对应的区间，将它们拆成三个无交的区间，拆完就可以区间 dp 了。进一步的，如果有交，我们可以通过上述的操作，外加一些讨论，将其转化为一个方案数不变但是容斥系数取相反数的情况，于是根本就不用考虑区间有交的情况。
P8478 「GLR-R3」清明（乘法分配律）
题目大概能表述为，确定具体流水方案后，求一堆多项式的乘积。直接施乘法分配律，变成确定方案后每个位置还要选一个雨水，再独立成确定某个阶梯的水流到某个子集的雨水的值的乘积与没流到子集中的雨水的方案数的乘积。使用生成函数计算可得，或者使用 组合意义 推导可得一个组合数。
然后就交给状压 dp 了。根号分治，\(k\) 小的时候记这个阶梯的后 \(k\) 个的情况，\(k\) 大的时候记 \([k+1, n]\) 阶梯的情况，\([1, k]\) 的只记选过的数量。然后写一些高维前缀和再优化一下常数即可通过，复杂度有一堆 \(n\) 因子都没有关系。
P4931 [MtOI2018] 情侣？给我烧了！(加强版)（错排）
直接推导 二项式反演 比较简单，然后发现只能过简单版。所以你考虑使用 NTT 优化，发现过不去，所以只能弃暗投明，使用 Elegia 法 或者别的什么东西可以推导出二项式反演对应的系数，也就是错排公式。
错排，还是太有用，直接省略容斥部分。
qoj 5357. 芒果冰加了空气（刻画）
你发现两个连通块对应的点分树合并时，假如中间那条边是 \((u, v)\)，则一旦分治中心再次选到 \(u, v\)，之后就完全确定了。所以只有 \(u, v\) 在原来连通块上的深度是重要的，记下来之后直接 dp。真是太神奇了。
P10104 [GDKOI2023 提高组] 异或图（数位 dp、容斥）
你发现这题 \(m=0\) 都挺难做，所以 \(m=0\) 应该怎么做？你想做数位 dp，如果你继续想一下，可以发信啊，一旦有一个数不顶上界了，就可以让其他数随便填，然后这个数下面的位根据实际情况调整。而没有顶上界之前，决策都是较为固定的，所以可以枚举在哪一位开始有人不顶上界，在那一位上做 \(O(n)\) 的小 dp，总复杂度 \(O(n\log C)\)。
\(m>0\) 时，直接施容斥吧，枚举边集的一个子集，要求里面的数全部相同，就相当于划分出很多连通块（每个连通块有一个系数，表示能是连通块连通的边集的容斥系数之和，此后全都改为对点集划分，这部分随便做），删掉偶数大小连通块，奇数大小只保留最小值。那么可以 \(\widetilde O(4^n)\) 做这个鬼东西，瓶颈是无法区分保留的最小值和已经选的。不妨对 \(a_i\) 排序，dp 到 \(i\) 的时候，记录前 \(i\) 个是否是最小值以及后 \(n-i\) 个是否选择过，这样就不会混淆，用 \(\widetilde O(2^n)\) 的空间存下所有状态，转移枚举子集所以时间复杂度 \(O(3^nn+2^nn\log C)\)。
Baekjoon 23510 Wise man（数位 dp）
你首先发现这个题在 QOJ 没有，很生气，然后也不太会做。肯定有一个想法是从低到高地去顶 \(M\)，但是状态有点多，和暴力一样，我们需要一个更有针对性的状态，要求它不能有太多不确定因素，然后需要能方便的支持跳转到对某一位进行 \(+1\) 后的情况。
\(dp[j][i][x]\) 表示当前这个数的个位（第 \(0\) 位）为 \(x\)，接下来 \([1, i]\) 位全零，\((i, +\infty]\) 的数位最大值为 \(j\)，对这样的数字使 \(i+1\) 位 \(+1\) 需要的步数以及 \(x\) 会变成什么样（发现这足够了，因为每次只会加 \([0, 9]\)）。可以轻易转移。可以轻易使用这个结果进行操作。
有一个循环的问题，你发现发生 \(\geq M\) 的操作去 \(-M\) 时，只会到达 \([0, 8]\) 的 \(A\)。多次 \(-M\) 的过程中，可以找出那个环，快速跳跃。于是可以通过。
（skipped）P5417 [CTSC2016] 萨菲克斯·阿瑞
skipped
CF1456E XOR-ranges（数位 dp、独立性）
无限制的位可以轻松删掉，我们要不对每个数处理出 \(O(m)\) 种情况，每种情况都形如固定了这个数的一个后缀（一堆高位），然后没固定的地位可以随便填。好的，这样就发现变成了和一个最值有关的类似笛卡尔树的结构，记录两边的状态，从中间枚举一个比它们高的状态断开，计算贡献，复杂度大概 \(O(n^6)\sim O(n^7)\)（视 \(n, m\) 同阶），很难受。
发现每一位是独立的，很诱人，我们删掉状态里的两个 \(n\) 和转移里的一个 \(n\) 将其改为一个 \(n\) 表示当前只考虑低 \(b\) 位。这样的话就好一点，两边的状态在记下 \(l, r\) 后直接变成 \(O(1)\)，然后可以转移，要么宣布这一位考虑完了，要么从中间找一个断点分割。复杂度 \(O(n^4)\)。
（skipped）CF1081G Mergesort Strikes Back
skipped