洛谷P1521求逆序对
867+
作者：crxis 发布：2021-04-28 分类：递推
题目大意：n的排列中，有多少个排列的逆序对数量恰好是m个？
题目描述
我们说（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以后再输出！
输入输出样例
输入 #1
5 3
输出 #1
15
解题思路
递推：从前一个状态推出后一个状态。f[i][j]表示i的排列中，有多少个逆序对数量为j的排列，每一个状态不重复，也不遗漏任何一个排列。加入数字i+1后，这个数字可以插入到i个数的旁边，如果插入到第k个位置，那么该位置前面共有k个数，多产生k个逆序对，之前有j个逆序对，现在有j+k个，得到状态f[i+1][j+k]，方案累加取模即可。
程序实现
