P1521 求逆序对

admin

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