MT与OI

【问题描述】

在MT刚接触到了冒泡排序的时候,觉得这个东西太慢了,但是加上break的效果怎么样呢?于是他开始考虑这样一个问题:任意一个N的排列中,有多少种需要恰好扫K次才能使得数列从小到大排列。所谓扫就是第一重循环,当数列有序后程序会自动退出循环。

冒泡排序代码(略)

【输入格式】

第一行一个数T,表示数据组数

接下来T行,每行两个整数N,K

【输出格式】

T个数,表示答案mod 1000000007

【数据说明】

30%:T<=10,N<=7

100%:T ≤ 100,000

1 ≤ N ≤ 1,000,000, 0 ≤ K ≤ N – 1

【题解】

一开始打表找到了一个递推公式。。

然后发现n方还是过不了。。和暴力一样的分数

正解:

首先定义d[i]为第i位的数前面有多少数大于该位的数。那么通过观察冒泡排序发现,每一次排序后若d[i]不为0则d[i]会减1,即有一个比它大的数穿过它从前面移到了后面。

那么问题就是:1~n的全排列中d[i]的最大值为k的数目。

再观察一下:d[1]只能取0,d[2]能取0或1,d[3]能取0,1,2…

那么对于d[1]~d[k],最大值必然小于k,总的组合数为k!。

对于d[k+1]~d[n],最大值小于等于k的组合数之和为\((k+1)^{n-k}\)。

那么答案就等于\(k!(k+1)^{n-k}\)

了吗?

并不是:这个只是最大值小于等于k的方案数,再将它减去最大值小于等于k-1的方案数即为所求。

即\(k!(k+1)^{n-k}-(k-1)!k^{n-k+1}\)

化简得\(k!((k+1)^{n-k}-k^{n-k})\)

预处理出阶乘,再快速幂即可。

说点什么

您将是第一位评论人!

提醒
wpDiscuz