华师一附中OI组

标题: P1521 求逆序对 [打印本页]

作者: admin 时间: 2019-10-23 20:25
标题: P1521 求逆序对
https://www.luogu.org/problem/P1521

题目描述
我们说（i，j）是a1，a2，…，aN的一个逆序对当且仅当i<j且ai>a j。例如2，4，1，3，5的逆序对有3个，分别为（1，3），（2，3），（2，4）。现在已知N和K，求1…N的所有特定排列，这些排列的逆序对的数量恰好为K。输出这些特定排列的数量。

例如N=5，K=3的时候，满足条件的排列有15个，它们是：

1，2，5，4，3
1，3，4，5，2
1，3，5，2，4
1，4，2，5，3
1，4，3，2，5
1，5，2，3，4
2，1，4，5，3
2，1，5，3，4
2，3，1，5，4
2，3，4，1，5
2，4，1，3，5
3，1，2，5，4
3，1，4，2，5
3，2，1，4，5
4，1，2，3，5
输入格式
输入第一行有两个整数N和K。（N≤100，K≤N*(N-1)/2）

输出格式
将1…N的逆序对数量为K的特定排列的数量输出。为了避免高精度计算，请将结果mod 10000以后再输出！

输入输出样例
输入
5 3
输出
15

欢迎光临华师一附中OI组 (http://hsyit.cn/)