2015
05-23

# 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

#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;
}
}

,