// 题目大意：一个具有n个元素的排列，经过k趟bubble sort排到有序状态。求出满足此条件的排列个数模20100713的结果。

// 此题涉及两个组合数学问题，一个是反序表（逆序数）的概念和特点，一个是快速幂取模。

// 反序表的概念如下：
// a1,a2,...,an是集合{1,2,...,n}的一个排列。令b[j]为位于j左边但是大于j的元素个数，就能得到排列a1,a2,...,an的反序表b1,b2,...,bn。
// 比如说：排列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,2,...,n }上的一个排列。
// 反序表的第一个特点是：第1个元素的逆序数取值范围是[0,n-1]，第i个元素的逆序数取值范围是[0,n-i]，最后一个元素的逆序数只能是0。
// 反序表的第二个特点是：每个元素的逆序数取值是相互独立。反序表和排列之间一一对应。全排列个数是n!，因此反序表的个数也是n!。

// 回到题目，逆序数最大为k。那么当n-i<=k，即i>=n-k的时候，元素i可随意放。因为不管怎么放，他们的逆序数都不会大于k，取值的个数由i来决定。
// 当i<n-k时候，这些元素的逆序数只可以在[0,k]之间选择。、
// 这样，把n个元素分为两类来讨论，前面一类元素有k+1（即i = n-k ~ n）个，后面一类有n-k-1（即i = 1 ~ n - k - 1）个元素。
// 先考虑前面一种情况，我们对最大的k+1个元素进行全排列，它们的逆序数一定在0~k之间，那么就有(k+1)!种排序的方法。
// 例如集合{1、2、3、4、5、6、7、8、9}，n为9，假设k为3，前一类元素有4个，分别是6、7、8、9，后一类元素有5个，分别是4、3、2、1、5，
// 首先，对前一类元素（6、7、8、9）随意放，逆序数都不会大于3，放置方法有4!种，

// 后面一类的每一个元素，按照从大到小的顺序插入前一类元素构成的某种排列，每一次插入都是插在已得到的某种不完整排列的前k+1个数之前，因此，有k+1种可选的位置。
// 例如（1、2、3、4、5）中，按照从大到小的顺序，5能插在6、7、8、9的前面，4能插在5、6、7、8、9的某个排列的前4个数前面，……，1能插在2、3、4、5、6、7、8、9的某个排列的前4个数前面
// 因此有(k+1)^(n-k-1)种方案。
// 由乘法原理，易得不超过k趟排到有序状态的排列的个数为：(k+1)! * ((k+1)^(n-k-1)) = k!*(k+1)^(n-k)。
// 但是题目要求出正好经过k趟排到有序状态的排列的个数，于是再求出不超过k-1趟排到有序状态的排列的个数为：(k-1)!*(k)^(n-k+1)。
// 两者相减，得到正好经过k趟排到有序状态的排列的个数为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;

long long fact[1000005] = { 0 };

// 计算m的n次方对k取余数的结果
long long QuickPowAndMod(long long m, long long n, long long mod)
{
	long long ans = 1;
	while (n)
	{
		if (n & 1)
		{
			ans = (ans * m) % mod;
		}
		n = n >> 1;
		m = (m * m) % mod;
	}
	return ans;
}

void GetFactModArr(long long fact[], int length, long long mod)
{
	fact[0] = 1;
	for (int i = 1; i <= length; i++)
	{
		fact[i] = (fact[i - 1] * i) % mod;
	}
}

int main()
{
	const long long mod = 20100713;
	GetFactModArr(fact, 1000000, mod);
	long long t = 0;
	//cin >> t;
	scanf("%I64d", &t);
	for (long long i = 0; i < t; i++)
	{
		long long ans = 0;
		long long n = 0, k = 0;
		//cin >> n >> k;
		scanf("%I64d %I64d", &n, &k);
		if (k == 0)
		{
			ans = 1;
		}
		else
		{
			// 计算 (k!*((k + 1)^(n - k)-k^(n - k))) % 20100713
			long long ans1 = fact[k], ans2 = fact[k];
			ans1 *= QuickPowAndMod(k + 1, n - k, mod);
			ans1 %= mod;
			ans2 *= QuickPowAndMod(k, n - k, mod);
			ans2 %= mod;
			ans = (ans1 - ans2 + mod) % mod;
		}
		//cout << ans << "\n";
		printf("%I64d\n", ans);
	}
	return 0;
}

• Re:我来个最详细的解题报告 (2790) HanwGeek 2019-03-06 16:46:19