「LOJ 6077」「2017 山东一轮集训 Day7」逆序对
题解
考虑已经有一个 \([1,i-1]\) 的排列，我们把 \(i\) 这个数插进去，会使得逆序对数量加 \(x_i\)，其中 \(x_i\in [0,i)\)。那么问题转化成求 \(\sum_{i=1}^n x_i=k\) 的解的数量，满足 \(\forall i\in [1,n]:0\le x_i < i\)。
考虑容斥，枚举不满足条件的位置个数 \(i\) 和位置 \(p_1,p_2,p_3,\cdots,p_i\)，那么问题变成了有若干个有 \(n\) 个条件，其中有 \(i\) 个条件是 \(x_{p_j}\ge p_j\)，其他条件是 \(x_j\ge 0\)。我们让 \(k\) 减去 \(p_1+p_2+p_3+\cdots+p_i\) 的值，就变成了一个经典的隔板法求不定方程非负整数解的数量的问题。即答案是
\[ans=\sum_{i=0}^{n}(-1)^i\sum_{p_1 < p_2 < p_3 < \cdots < p_i} C_{n-1+k-\sum_{j=1}^i p_j}^{n-1}\]
我们发现后面的组合数式子不需要关心 \(p_j\) 具体的值，只需要知道 \(\sum_{j=1}^i p_j\) 即可。于是我们枚举这个值，式子变成了
\[ans=\sum_{i=0}^n(-1)^i\sum_{j=0}^{k}F_{i,j}C_{k-j+n-1}^{n-1}\]
其中 \(F_{i,j}\) 表示选 \(i\) 个互不相同的数，且这些数在 \([1,n]\) 的范围内，使得这 \(i\) 个数和为 \(j\) 的方案数。又可以注意到，因为 \(i\) 个数要互不相同，所以当 \(j < \frac{i(i+1)}{2}\) 时，\(F_{i,j}=0\)。又因为 \(j\) 不能超过 \(k\)，所以 \(i\) 只需要枚举到 \(\lfloor\sqrt{2k}\rfloor\) 即可。而组合数可以 \(O(n+k)\) 预处理阶乘及阶乘的逆元，然后 \(O(1)\) 计算。那么关键问题是如何求 \(F_{i,j}\)。
这是经典的整数划分问题。假设当前有 \(i\) 个数，和为 \(j\)，那么有两种决策：
- 把所有数加 \(1\)，和变成了 \(i+j\)；
- 在最前面加上一个数 \(1\)，并把其他所有数加 \(1\)，个数变成 \(i+1\)，和变成 \(i+j+1\)。
可以证明所有方案都可以通过这两种变换唯一的遍历到。但是有些方案中会存在某个数大于 \(n\) 的情况，需要减去。又因为所有数互不相同，且变换之前的方案是合法的，所以这个不合法的方案一定只会存在一个大于 \(n\) 的数且这个数是 \(n+1\)。那么这种不合法的方案数一定与去掉 \(n+1\) 这个数后序列的方案数相等，直接减去即可。DP 的转移方程是
\[F_{i,j}=F_{i,j-i}+F_{i-1,j-i}-F_{i-1,j-n-1}\]
可以直接带上容斥系数，变成
\[F_{i,j}=F_{i,j-i}-F_{i-1,j-i}+F_{i-1,j-n-1}\]
处理完后直接计算即可。时间复杂度 \(O(n\sqrt{n})\)。
还有一种用生成函数推导答案式子的方法，可以参考 Trisolaris's Blog。
代码
1 |
|
