【UVA 11077】 Find the Permutations (置换+第一类斯特林数)

Find the Permutations

Sorting is one of the most used operations in real life, where Computer Science comes into act. It is well-known that the lower bound of swap based sorting is nlog(n). It means that the best possible sorting algorithm will take at least O(nlog(n)) swaps to sort a set of n integers. However, to sort a particular array of n integers, you can always find a swapping sequence of at most (n − 1) swaps, once you know the position of each element in the sorted sequence. For example consider four elements <1 2 3 4>. There are 24 possible permutations and for all elements you know the position in sorted sequence. If the permutation is <2 1 4 3>, it will take minimum 2 swaps to make it sorted. If the sequence is <2 3 4 1>, at least 3 swaps are required. The sequence <4 2 3 1> requires only 1 and the sequence <1 2 3 4> requires none. In this way, we can find the permutations of N distinct integers which will take at least K swaps to be sorted. Input Each input consists of two positive integers N (1 ≤ N ≤ 21) and K (0 ≤ K < N) in a single line. Input is terminated by two zeros. There can be at most 250 test cases. Output For each of the input, print in a line the number of permutations which will take at least K swaps.

Sample Input

3 1

3 0

3 2

0 0

Sample Output

3

1

2

【题意】

给出1~n的一个排列，可以通过一系列的交换变成{1,2,…,n}。比如{2,1,4,3}需要两次交换。给定n和k，统计有多少个排列至少需要k次交换才能变成{1,2,…,n}。

【分析】

　　先考虑一下怎么计算最少变换次数。

　　显然，如果把它弄成x个循环的乘积，最少变换次数为n-x。

　　问题变成了，给你n个数，分成n-x份的圆排列方案。这个方案刚好就是第一类斯特林数啊。

　　所以很简单，用第一类斯特林数的方程求方案就行了。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define LL unsigned long long

 #define Maxn 

 LL s1[][];

 void init()

 {

     memset(s1,,sizeof());

     s1[][]=;

     for(int i=;i<=;i++)

      for(int j=;j<=;j++)

         s1[i][j]=s1[i-][j-]+s1[i-][j]*(i-);

     // printf("==%lld\n",s1[2][0]);

 }

 int main()

 {

     init();

     int n,k;

     while()

     {

         scanf("%d%d",&n,&k);

         if(n==&&k==) break;

         printf("%llu\n",s1[n][n-k]);

     }

     return ;

 }

注意要用unsigned long long ，还是看了别人的代码才知道的。。。不然会WA、。。。。

其实这题只是用了小小的置换的思想而已。

2017-01-11 19:16:56

巴特西

【UVA 11077】 Find the Permutations (置换+第一类斯特林数)

最新文章

热门文章