频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
POJ 3761 Bubble Sort (用反序表分析排列数)
2013-12-03 15:29:56         来源:AC,∑ndless  
收藏   我要投稿

 

 

 

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

由乘法定理,得反序表数为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. 编程时先预处理阶乘再用快速幂取模计算求幂部分。

 

完整代码:

 

/*454ms,7984KB*/

#include
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
, factorial[k] * ((mpow(k + 1, n - k) - mpow(k, n - k) + mod) % mod) % mod);
	}
	return 0;
}

 

 

点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:LeetCode Search for a Range搜索特定数值的范围 三种方法求解
下一篇:hdu3861The King’s Problem
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站