poj3761（反序表）

题目链接：https://vjudge.net/problem/POJ-3761

题意：给出n和k，求通过k趟冒泡排序得到长为n的有序排列（元素为n个不同的数）的原排列有多少个。

思路：

先给出反序表的定义：

　　令bi(1<=i<=n)為位於i左邊但是大於i的元素個數，就能得到排列a1,a2,...,an的反序表b1,b2,...,b3。比如說，排列5 9 1 8 2 6 4 7 3有反序表2 3 6 4 0 2 2 1 0（在1左邊且大於1的有2個，在2左邊且大於2的有3個，……）。

再给出反序表的重要结论：

　　第1個元素的反序數取值範圍是[0,n-1]，第i個元素的反序數取值範圍是[0,n-i]，最後一個元素的反序數只能是0。并且每個反序數可以在區間內任意取值而不用考慮其他反序數的值，也就是說反序數是相互獨立的。（因为第一个元素的反序数[0,n-1]分别对应n个位置中的一个位置，确定之后去掉这个位置，剩下n-1个位置; 第二个元素的反序数[0,n-1]对应这n-1个位置中的一个，确定之后去掉这个位置，剩下n-2个位置......这样可以得到所有反序表对应的原排列有n!个，原排列本身最多只有n!个，所以反序表和原排列是一一对应的，且反序表中反序数相互独立。）

回到题目：

　　不难发现每一趟冒泡排序都会将剩下的>0的反序数减一，所以题目就转变乘最大反序数为k的反序表个数。所以我们可以通过求最大反序数<=k的反序表的个数，元素i的反序数为n-i，令n-i<=k得i>=n-k，即>=n-k的元素其反序数恒<=k，所以其反序数的值可以是其范围内的任意值，共有(k+1)!种可能。对于i<n-k，其反序数范围为[0,k]，即k+1种，则共有(k+1)^(n-k-1)种可能。两者相乘得k!*(k+1)^(n-k)。

　　同理求出最大反序数<=k-1的个数，相减得k!*[(k+1)^(n-k)-k^(n-k)]。

　　然后打表阶乘，利用快速幂取模即可。

AC代码：

#include<cstdio>

using namespace std;

typedef long long LL;

const int maxn=;

const int Mod=;

int T;

LL f1[maxn];

void init(){

    f1[]=f1[]=;

    for(int i=;i<=;++i)

        f1[i]=f1[i-]*i%Mod;

}

LL qpow(LL a,LL b){

    LL ans=;

    while(b){

        if(b&) ans=(ans*a)%Mod;

        a=(a*a)%Mod;

        b>>=;

    }

    return ans;

}

int main(){

    init();

    scanf("%d",&T);

    while(T--){

        LL n,k;

        scanf("%lld%lld",&n,&k);

        printf("%lld\n",f1[k]*(qpow(k+,n-k)-qpow(k,n-k)+1LL*Mod)%Mod);

    }

    return ;

}

巴特西

poj3761（反序表）

最新文章

热门文章