P2513题解

· · 个人记录

非常有意思的一道题目。题解区里好像没有与我的做法类似的，我来讲讲我的做法。

分配

看到题面，发现这个长度为 n 的序列有 k 个逆序对。那么我们考虑“分配”逆序对，即考虑每个位置前有多少个数值比他小的数。

猜想

合法的分配方案都与合法的序列形成一一映射关系，即可以通过每一种合法的分配方案推导至唯一确定的合法序列。

证明

我们假设现在有一个合法的分配方案，要我们求他对应的合法序列。

首先我们维护一个序列 v , v 里的值表示序列位置序号，而 v 的顺序表示一个大小关系，即 v 中每一个元素所对应的位置的值单调递减。 v 初始为空。

接着，我们从头扫描这个合法的分配方案。设第 i 位为 p_i ，则将 i 插入在 v 中第 p_i 个元素之后。

最后，我们根据 v 给每一个位置赋值，就得到了一个合法的序列。

由于分配方案是确定的，那么 v 也是确定的，且由于不可能有另一个合法的 v ，最终的序列也是确定的。

综上，合法的分配方案都与合法的序列形成一一映射关系。

计算

根据前面所说的，我们可以把题目等价于求有多少个长度为 n 的序列，总和为 k 。但是注意到这里还有一个隐蔽的条件，第 i 位上的值不能有超过 i-1 。

考虑通过 dp 计算。设 dp_{i, j} 表示前 i 个位置总和为 j 的方案数。转移很简单。由于朴素转移是 O(n^3) 的，太慢，所以使用前缀和优化。

代码非常简单，就不放了。