本文主要是介绍poj3761 bubble sort，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：已知N，对N的一个排列进行冒泡排序，共K趟后排成升序，求一共有多少个这样的排列(mod 20100713)。
最开始我沙茶地得出了个结论，一趟就是最大值沉底，其它不变，因此和最长下降子序列有关（其实选择排序应该是这样）。然而实际上不是。每排一趟，一个数的逆序数最多-1（沉底那个除外），因此题目就是让你构造逆序数最多的一个数的逆序数是K的N排列。
设f(i,K)为前i小的数进行排列，其中逆序数最大的一个数的逆序数小于等于K的方案数。当i小于等于K时，显然无法使得任意数的逆序数超过K，故f(i, K) = f(i-1, K) * i; i>K时，考虑将i放入这个排列，因为i是目前最大一个数，所以要使得i处于最后K+1个位置才能保证在i后面的之前放的数不超过K个。通项易得为f(N, K) = K!*(K+1)^(N-K)。然而这只是最大逆序数小于等于K的方案数，这题最巧妙的地方就是恰好等于K的方案数可以作差求得，为f(N,K)-f(N,K-1)。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
const LL tsy = 20100713;
const int MAXN = 1000010;
int T;
LL N, K;
LL jc[MAXN];
LL ksm(LL a, LL b)
{LL res = 1;for (; b>0; b>>=1, a=a*a%tsy)if (b&1) res = res * a % tsy;return res;
}
inline LL getx(LL n, LL k) {return jc[k] * ksm(k+1, n-k) % tsy;
}
int main()
{scanf("%d", &T);jc[0] = 1;for (LL i = 1; i<MAXN; ++i)jc[i] = jc[i-1] * i % tsy;while (T--) {scanf("%I64d%I64d", &N, &K);LL ans = (getx(N, K) - getx(N, K-1)) % tsy;printf("%I64d\n", (ans + tsy) % tsy);}return 0;
}
这篇关于poj3761 bubble sort的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
