首页 > 代码库 > uva 11077 置换

uva 11077 置换

 1 /**
 2 给定一个置换,看能不能存在一个置换A^2 = B
 3 思路; 循环节长度为偶数n的置换只能由循环节长度为长度2*n 的置换A*A 而变得。所以只需求出循环节,看循环节长度为偶数的个数是否为偶数个即可。。
 4 训练指南
 5 **/
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 using namespace std;
10 const int maxn = 30;
11 
12 unsigned long long f[maxn][maxn];
13 int main()
14 {
15     memset(f,0,sizeof(f));
16     f[1][0] = 1;
17     for(int i=2;i<=21;i++){
18         for(int j=0;j<i;j++){
19             f[i][j] = f[i-1][j];
20             if(j>0) f[i][j] += f[i-1][j-1]*(i-1);
21         }
22     }
23     int n,k;
24     while(cin>>n>>k){
25         if(n==0&&k==0)
26             break;
27         cout<<f[n][k]<<endl;
28     }
29     return 0;
30 }