POJ 3761 Bubble Sort 快速幂取模+组合数学
2018-06-27 09:59:04来源:未知 阅读 ()
转载于:http://www.cnblogs.com/767355675hutaishi/p/3873770.html
题目大意:众所周知冒泡排序算法多数情况下不能只扫描一遍就结束排序,而是要扫描好几遍。现在你的任务是求1~N的排列中,需要扫描K遍才能排好序的数列的个数模20100713。注意,不同于真正的冒泡排序算法,只要数列有序就立刻停止,而不用再检验一遍。
估计多数人都是找规律吧,先看出递推,然后求出通项……这个题只有找出通项公式才能通过,所以首先公布答案:
K!((K + 1) ^ (N - K) - K ^ (N - K))
好吧,现在让我们来证明一下。
首先定义函数d(x),对于1~N的一个排列,d(x)表示第x个数前面有多少个数字大于该数。
比如说对于3 2 4 1 5,有d(1) = 0,d(2) = 1,d(3) = 0,d(4) = 3,d(5) = 0。
现在我们来证明d(x)函数的两条性质:
(一)对于一个排列,对于所有x <= N,有d(x) = 0是这个排列是有序的充要条件。
如果存在1 <= i, j <= N,使得i < j,ai > aj,那么由于aj前面有ai大于它,故d(j) >= 1。而这与d(j) = 0矛盾,反之亦然。所以说命题成立。
(二)冒泡排序的每次扫描的结果是,对于非零的d(x)值,这个位置的d(x)会且只会减少1。
考虑某个非零的d(x)值。由于d(x) >= 1,所以必然存在整数i∈[1, x - 1],满足ai > ax。设m为a1, a2, ..., a(x -1)中的最大值,位置为i,则必有m > ax。那么,在扫描到a(x - 1)和ax的时候,由于前面的交换,必然有a(x - 1) = m。
原因是如果前面的交换将m交换到了a(x - 2)的位置,那么由于m > a(x - 1),那么ai必然能够被交换到a(x - 1)的位置。故由数学归纳法,只要m能够被交换到a(i + 1)即可。而在交换之前a(i - 1) < m,m与a(i - 1)不发生交换;同时必然有m > a(i + 1),m一定会被交换到a(i + 1),故该结论成立,从而扫描a(x - 1)和ax的时候a(x - 1) = m。
这时由于m > ax,m与ax之间要交换,交换的效果由于ax前面比ax小的数字减少了一个,d(x)减小了1。所以说d(x)在这个过程中必会减少。
而另一方面,完成了m与ax的这次交换之后,这一次扫描显然就不会再交换ax的值了(这时ax位置上的值已经是m了)。所以说,d(x)也只能减少1。这就证明完毕。
证明了d(x)函数的这个性质之后,我们就可以得出对于1~n的一个排列,它所需要的冒泡排序的扫描次数为
K = max (d(i), 1 <= i <= N)
而这个结论很显然,因为只有经过K次扫描,所有位置的d值才能都变为0。
到此,我们成功地将冒泡排序的次数问题转化为d(x)值满足条件的数列的问题。原问题也就转化成了有多少个排列使得其中最大的d(x)值恰好为K。然而这也是复杂的,所以说我们不妨先解决有多少个排列使得其中最大的d(x)值不大于K。
首先可以确定N >= K + 1,否则不可能出现某个位置前面有K个数大于它。
然后决定原数列中1的位置。显而易见,如果最小数的位置为x,则其d(x) = x - 1。而d(x) <= K,故x <= K + 1,也就是说1有K + 1种放置方法;而放置2的时候,我们完全可以考虑一个新的排列2~N,这时2有K + 1种放置方法,然后再把1插到位置1~K + 1,而不影响其它数的d值。所以说,前N - K个数的放置方法的种类有
(K + 1) ^ (N - K)
之后只需要考虑N - K + 1 ~ N的排列即可。然而,由于整个数列只有K个数字,不可能出现某个d值大于K + 1。所以说排列方法有K!种。故,所有位置d值不大于K的排列的方案数有
K!((K + 1) ^ (N - K))
但是这是不大于K的排列数量,恰好为K的有怎么办呢?很简单,只需要减去不大于K - 1的排列数量便可。所以最后的答案为
K!((K + 1) ^ (N - K)) - (K - 1)!(K ^ (N - K + 1))
化简之后我们就得到
K!((K + 1) ^ (N - K) - K ^ (N - K))
这就是原来的式子,它的正确性就证明完毕。
#include <iostream> #include <cstdio> using namespace std; const int Mod=20100713; __int64 fac[1000005]= {1}; __int64 Power(__int64 a,__int64 k) { __int64 ret=1; for(; k; k>>=1) { if(k&1) ret=ret*a%Mod; a=a*a%Mod; } return ret; } int main() { for(int i=1; i<1000001; i++) fac[i]=fac[i-1]*i%Mod; int t; scanf("%d",&t); while(t--) { int n,k; scanf("%d%d",&n,&k); printf("%I64d\n",(Power(k+1,n-k)-Power(k,n-k)+Mod)%Mod*fac[k]%Mod); //Power(k+1,n-k)-Power(k,n-k)可能小于零
} return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash