[逆序]POJ_3761
题目大致意思就是:求1,2,3…..N有多少个排列是用冒泡排序只需要k轮就好的.给定一个n和一个k,然后让你输出答案模上一个数.因为答案是在太大了
这里首先给出公式吧对给定的n和k,答案是k!*((k+1)^(n-k)-k^(n-k)).
ps:以下分析借助了<计算机程序设计艺术>和这篇博文
首先我们知道对于每个排列和其逆序对是一一对应的.也就是说一个逆序对对应一个排列,一个排列对应一个逆序对,相同排列的逆序是一样的,同一个逆序对的排列也是一样的.下面我们来看看这个和逆序对有啥关系.这里以4 5 3 1 2这个排列为例.那么逆序对为3 3 2 0 0.也就是1的逆序数为3,2的为3,依次下去.那么我们来看下依次冒泡排序会改变什么,首先第一趟我们会发现变成了4 3 1 2 5.那么逆序对变成了2 2 1 0 0也就是所有逆序数>0的都-1了,这个是偶然吗?不是的,因为对于每一趟冒泡,都有一个当前未排好序的最大的沉到最下面去,这样就会导致这个当前最大的数的后面的那些数的逆序数都会-1.上面的当前最大就是5,5后面的是3 1 2,所以3 1 2这几个数的逆序数都会-1.OK,现在我们知道,对于每趟冒泡排序,所有逆序数不为1的都会-1,那么体重要求的我们可以转化成求这样的排列的个数:也就是逆序数的最大值为k的n个数的一个排列.这样我们就得到了一个冒泡最多需要k次的一个排列,而且逆序数和排列是一一对应的,所以我们得到的”逆序数的最大值为k的n个数的排列”的个数就是本题的答案.
现在的问题变成了求逆序数的最大值为k的n个数的排列的个数,也就是给你n个位置,这n个位置上可以放置一系列数,但是最大为k,最小0的排列的数目,而且我们这里要求的是至少要有一个数=k(不然不需要k趟就排完了).那么我们可以考虑用最大的为k减去最大的为k-1的排列,剩下的就是至少有一个最大值为k的了.现在我们求最大值为k,但不一定有最大值为k的排列的数目.我们可以这么想:对于1,有逆序数为0,1…..k这些选择,也就是它的位置可以选择为0 1 2…k(位置从0开始),放置好1之后,我们再放2,同理可以得到一系列的位置,也就是2也可以有k+1中选择,知道某个数不可能出现逆序数为k为止,那么我们知道一个数的最大逆序数位n-i(i是这个数,这里的环境都是1,2….n这样的排列).那么最大的i就是k了.所以这里有(k+1)^(n-k),然后剩下的就自己选位置吧,有k!种方案,所以就是k!((k+1)^(n-k)).那么我们的结果就是k!(k+1)^(n-k)-(k-1)!k^(n-k+1)然后化简就变成了k!((k+1)^(n-k)-k^(n-k))到这里这题也结束了,不过还有一点,在保证不会越界的情况下,能不用mutil_mod(算a*b%c),这类的函数就不用,所有函数都是有开销的,别到时TLE了还找不到原因
