http://poj.org/problem?id=3761
1. 先介绍反序表的概念：
令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个，……）
2. 关键结论：
由1知，第1个元素的反序数取值范围是[0,n-1]，第i个元素的反序数取值范围是[0,n-i]，最后一个元素的反序数只能是0
（注意，每个反序数可以在区间内任意取值而不用考虑其他反序数的值，也就是说反序数是相互独立的。理由是反序表的个数亦为n!，而排列和反序表是一一对应的关系。）
3.
不难发现，每一趟bubble sort ，都会将反序数大于0的元素的反序数减1。若经过k趟之后排好序，则说明反序表中最大值为k。
因此，题目可以转化为，已知n个元素的排列的反序表中最大值为k，求这样的排列有多少种。
4. 现在来求反序数不超过k的反序表数：
因为反序数不超过k，那么当n-i<=k，即i>=n-k的时候，元素i可随意放。因为不管怎么放，他们的反序数都不会大于k，取值的个数由i来决定，所以反序表有Π(n-i+1)=(k+1)!种（n-k<=i<=n）。
而当i<n-k，因为反序数不超过k，这些元素的反序数只可以在[0,k]之间选择，所以反序表有(k+1)^(n-k-1)种。
由乘法定理，得反序表数为k!*(k+1)^(n-k)。
5. 但我们必须保证有一个元素的反序数为k，怎么做？
很简单，计算出反序数不超过k-1的反序表数，与4中结果相减，即为最终结果。
ans=k!*(k+1)^(n-k)-(k-1)!*(k)^(n-k+1)=k!*((k + 1)^(n - k)-k^(n - k))
6. 编程时先预处理阶乘再用快速幂取模计算求幂部分。
完整代码：
[cpp]view plaincopyprint?
/*454ms,7984KB*/
#include<cstdio>
typedef __int64 ll;
const ll mod = 20100713LL;
const int maxn = 1000001;
ll factorial[maxn] = {1LL};
inline ll mpow(ll a, int n)
{
ll ans = 1LL;
while (n)
{
if (n & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
int main()
{
int t, n, k;
ll ans;
for (int i = 1; i < maxn; ++i)
factorial[i] = (factorial[i - 1] * i) % mod;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &k);
printf("%I64d\n", factorial[k] * ((mpow(k + 1, n - k) - mpow(k, n - k) + mod) % mod) % mod);
}
return 0;
}
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/