当前位置:首页 > 递推 > 正文
洛谷P1521求逆序对
148+

题目大意: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个,它们是:

12543    
13452   
13524   
14253   
14325   
15234   
21453   
21534   
23154   
23415
24135    
31254   
31425   
32145   
41235

输入格式

输入第一行有两个整数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],方案累加取模即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

洛谷P1521求逆序对:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter