我们说(i,j)是a1,a2,...,aN的一个逆序对当且仅当ia j.例如2,4,1,3,5的逆序对有3个,分别为(1,3),(2,3),(2,4).现在已知N和K,求1...N的所有特定排列,这些排列的逆序对的数量恰好为K.输出这些特定排列的数量.
例如N=5,K=3的时候,满足条件的排列有15个,它们是:
将1...N的逆序对数量为K的特定排列的数量输出.为了避免高精度计算,请将结果mod 10000以后再输出!
递推:从前一个状态推出后一个状态.f[i][j]表示i的排列中,有多少个逆序对数量为j的排列,每一个状态不重复,也不遗漏任何一个排列.加入数字i+1后,这个数字可以插入到i个数的旁边,如果插入到第k个位置,那么该位置前面共有k个数,多产生k个逆序对,之前有j个逆序对,现在有j+k个,得到状态f[i+1][j+k],方案累加取模即可.
洛谷P1521求逆序对:等您坐沙发呢!