题意 : 设 表示排列 的逆序对数。如果 长度为 则有 给定两个正整数 ，和一个排列 ，定义一个长度为 的排列 的权值 为
对于 求
其中 是长度为 的排列。
，时限 。
对于排列 ，定义
，即 与后方元素的逆序对数。
可以证明， 和 构成一一对应。
设 为 的逆排列，则 也和 构成一一对应。
记
，组合意义是 ：值
后方的逆序对数。
有（充要）约束 ： 。
故答案的生成函数为 ：
考虑分子分母分别计算。使用 :
分子：
暴力求和即是
的，注意要避免在复杂度瓶颈上直接快速幂。
分母：
即求出 的 次方和。
实现时注意将分子分母相减再 ，不要分别 。
复杂度
，注意常数。