POJ 3761 Bubble Sort 快速冪取模+組合數學

轉載於：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; }