Loj#6077. 「2017 山东一轮集训 Day7」逆序对

题意：求长为 的逆序对数恰好为 的排列个数。

答案对 取模。

，时限 。

---

默认 同阶。

对于排列 ，记 ，即 与前面的位置构成的逆序对数。

显然 有约束 。

• 结论：一组 和一组 构成双射。

  证明： 的映射由定义显然。考虑如何从一组 还原 。

  首先考虑 ，显然可得 。然后去掉 （并离散化）即变为子问题。

于是，原问题转化为对序列 的计数。

即方程 的解的个数。

写出生成函数的形式：

构造 则答案为 即 的系数和。

注意 的系数中 的次数至少是 ，故只需考虑到 的 次项。

有性质：

于是有：

从此处也能看出， 是 的倍数。

可以利用类似 完全背包/01背包 的方法 乘上。

边界是 。

故最终复杂度为 。可以求出 的答案。