首页 > ACM题库 > HDU-杭电 > HDU 4243-Maximum in the Cycle of 1-图-[解题报告]HOJ
2015
05-23

HDU 4243-Maximum in the Cycle of 1-图-[解题报告]HOJ

Maximum in the Cycle of 1

问题描述 :

If P is a permutation of the integers 1, …, n, the maximum in the cycle of 1 is the maximum of the values P(1), P(P(1)), P(P(P(1))), etc. For example, if P is the permutation:
    |1 2 3 4 5 6 7 8|
    |3 2 5 4 1 7 8 6|
we have:
  P(1) = 3
  P(P(1)) = P(3) = 5
and
  P(P(P(1))) = P(5) = 1
so the maximum in the cycle of 1 is 5.

For this problem, you will write a program which takes as input integers n, (n > 0) and k(1 <= k <= n), and returns the number of permutations of the integers 1, …, n, for which the maximum in the cycle of 1 is k.

输入:

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set is a single line that contains the three space separated decimal integer values. The first value is the data set number, N. The second value is the size of the permutation, n where (1 <= n <= 20), and the third value is the desired maximum in the cycle of 1, k where (1 <= k <= n).

输出:

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set is a single line that contains the three space separated decimal integer values. The first value is the data set number, N. The second value is the size of the permutation, n where (1 <= n <= 20), and the third value is the desired maximum in the cycle of 1, k where (1 <= k <= n).

样例输入:

4
1 4 1
2 7 3
3 10 5
4 20 7

样例输出:

1 6
2 168
3 86400
4 11585247657984000

题意:1~n的排列,求满足下述循环节里k最大的排列有多少种。

Maximum in the Cycle of 1

分析:题目不难,其实排列组合的问题不就是用高中的知识嘛。这题的关键是对这个循环节的理解,画个图就容易理解多了:1—>1;1—>k—>1;1—>x—>k—>1……循环节中必须保证k最大,所以循环节中除了1和k的其他元素肯定是在1~k中选择,那么枚举其他元素的个数,然后在1~k中选择,然后排列,其余的元素再全排列即可。特殊情况是1—>1,直接输出(n-1)!。排列组合的公式要记住,这是基本的。

代码:

#include<iostream>
using namespace std;
long long t,n,cas,k;
long long ans;
long long tmp1,tmp2,tmp3;
long  long  f(long long a)
{
	if(a==1||a==0) return 1;
	else return f(a-1)*a;
}
int main()
{
	cin>>t;
	while(t--){
		cin>>cas>>n>>k;
		if(k==1) ans=f(n-1);
		else{
			ans=0;
			for(int i=1;i<=k-1;i++){
				tmp1=f(k-2);
				tmp2=f(k-1-i);
				tmp3=f(n-i-1);
				ans+=tmp1/tmp2*i*tmp3;
			}			
		}
		cout<<cas<<" "<<ans<<endl;
	}
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/AC_0_summer/article/details/47127489


,