mzx 的动态规划杂题选讲。sto
ARC153 D - Sum of Sum of Digits
P7152 [USACO20DEC] Bovine Genetics G
CF1542E2 Abnormal Permutation Pairs (hard version)
题意
给定 \(n,m\)，求有多少对长度为 \(n\) 的排列 \(p,q\)，满足以下条件：
-
\(p\) 的字典序小于 \(q\)；
-
\(p\) 的逆序对个数 严格大于 \(q\)；
答案对 \(m\) 取模。\(1\le n\le 500\)，\(1\le m\le 10^9\)，不保证 \(m\) 为素数。
解法
发现这个题需要满足的条件有两个，直接一起做的话很困难，可以先思考满足其中一个条件时怎么做。
发现求的 \(p,q\) 是一个排列，而排列有一个很好的性质：在删去一些数后，因为我们只关心它们的相对大小关系，所以剩下的数也可以看做一个排列，这就是一个子问题了。
-
只用满足第一个条件：
- 这个字典序的限制很经典，可以枚举前多少位相同，前面的一样，后面的随便选。
-
只用满足第二个条件：
-
定义 \(f_{i,j}\) 表示有多少个 \(i\) 的排列刚好有 \(j\) 个逆序对。
-
如果你枚举每个位置放哪个数，就需要在状态中记录一个指数级别的维度表示哪些数被选了，这并不利于我们的转移；
-
考虑把这个看做在一个 \(i-1\) 的排列中插入一个 \(i\)。如果插在第 \(k\) 个数之后，就会增加 \(i-1-k\) 个逆序对。转移就是 \(f_{i,j}=\sum\limits_{k=0}^{i-1}f_{i-1,j-(i-1-k)}\)。这个转移是从连续的一段转过来的，可以前缀和优化，时间复杂度 \(O(n^3)\)。
-
现在我们同时考虑两个条件。假设 \(p,q\) 的前 \(i-1\) 位相同。此时，排列可以分成三部分：前 \(i-1\) 位，第 \(i\) 位，后 \(n-i\) 位。注意到 \(p,q\) 第一部分完全相同，所以其与二三部分的逆序对数相同，可以忽略。因此，我们需要考虑的逆序对数只由两部分构成：
-
第 \(i\) 位与后 \(n-i\) 位间的逆序对；
-
后 \(n-i\) 位中的逆序对；
因为排列的性质，后 \(n-i+1\) 位已经是独立的了。
-
假设 \(p,q\) 第 i 位填的是 \(k_1,k_2\)，则 \(p\) 就比 \(q\) 少了 \(k_2-k_1\) 个逆序对。
-
令 \(d=k_2-k_1\)，因为在取出第 \(i\) 位填的数后后 \(n-i\) 位与 \(i\) 位填的数的值没有关系，而逆序对数量只需要满足 \(p\) 比 \(q\) 多至少 \(d\) 个，我们只用枚举第 \(i\) 位的差值 \(d\)。此时，设 \(p\) 第三部分的逆序对数位 \(j\)，则 \(q\) 可选的方案共有 \(\sum\limits_{k=0}^{j-d-1}f_{n-i,k}\) 种。
整理一下，答案就是
其中 \(A_n^{i-1}\) 表示排列数。
这是一个 \(O(n^6)\) 的柿子，我们考虑优化。记 \(g_{i,j}=\sum\limits_{k=0}^jf_{i,k}\)，\(s_{i,j}=\sum\limits_{k=0}^jk\times g_{i,k}\)，\(t_{i,j}=\sum\limits_{k=0}^jg_{i,k}\)。
发现前面可以用 \(t\) 数组优化，后面可以用 \(s\) 数组优化。总时间复杂度 \(O(n^3)\)。
\(n^3\) 的数组开不下，需要一边求 \(f,g,s,t\) 的同时统计答案。
实际操作时需要考虑越界等无解的情况，处理比较繁琐，建议分段运算。
总结
-
对于多条件计数问题，通过分类讨论，枚举等方式降低条件的耦合度，独立解决低耦合度的问题并合并成最终问题的答案；
-
设计动态规划时要 考虑阶段本身的转移是否容易，本题转化后的基本问题中，如果按下标位置动态规划，阶段转移需要知道前面比该位置小的数的个数，需要记录的状态为指数级。如果按值的大小从小到大动态规划，转移时只需要枚举当前的数放在当前的哪个下标，需要记录的状态数为常数级；
-
看推柿子的思路；