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, 给定n和k，统计有多少个排列至少需要交换k次才能变成有序的序列。

题解： 

每个长度为n循环需要交换n-1次才能将交换到对应的位置，例如1->2,2->4,4->1,(1,2,4)位置上对应值为(2,4,1) 相当于一个长度为3的环逆时针旋转了1格，要变换回来，需要跟原位置交换，因为成环，所以共n-1次     那么对于序列P，有x个循环节，长度为n，就需要交换n-x次     对于f[i][j]，表示交换j次能变为1~i的序列的种数     我们找到递推式：f[i][j]=f[i-1][j]+f[i-1][j-1]*(i-1)，边界是f[1][0]=1,其余为0     解释：新增的i，如果与自己构成循环，那么循环数和长度都加一，交换数不变，所以是f[i-1][j]         新增的i，如果参加到其他环中，每个数后一种，共i-1种，循环数不变，长度加一，所以是f[i-1][j-1]*(i-1)     例如1->2,2->3,3->1,{2,3,1};将4添加到1后就是1->4,4->2,2->3,3->1，序列为{4,3,1,2};其他同上

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std ;typedef long long ll;const int N = 105;const int mod = 1e9 + 7;unsigned long long  dp[N][N];void init() {    for(int i = 1; i <= 21; i++) {        dp[i][0] = 1;        for(int j = 1; j < i; j++)            dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (i-1);    }}int main () {    init();    int n,k;    while(~scanf("%d%d",&n,&k)) {        if(n == 0 && k == 0) break;        printf("%llu\n",dp[n][k]);    }    return 0;}