HDUOJ 不容易系列之(4)——考新郎

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2049

一开始我的想法就是使用错排公式，先使用全排列从N对中选出M对，然后再使用错排对选出的M对进行错排计算，最后二者相乘。

emmm，代码写得很丑，只是提供一个思路，遇到类似的题目可以多一个思考方向。

D(n) = (n-1) [D(n-2) + D(n-1)]

特殊地，D(1) = 0, D(2) = 1.

详细推导过程百度一下你就知道。

 1 /*使用数学公式的思路比较简单，在N对中选择M对出来，也即是全排列的C(N,M),然后对这M对进行全错排，结果再将二者相乘；*/
 2 #include <iostream>
 3 using namespace std;
 4 int D(int n)         //全错排；
 5 {
 6     if(n==1)
 7         return 0;
 8     if(n==2)
 9         return 1;
10     else return 
11         (n-1)*(D(n-1)+D(n-2));     
12 }
13 int C(int n,int m)   //全排列
14 {
15     if(m==0)
16         return 1;
17     if(n==m)
18         return 1;
19     else return C(n-1,m)+C(n-1,m-1);
20 }
21 int main()
22 {
23     int i,n,m;
24     cin>>i;
25     int N,M;        //N是新人对数，M是找错的新郎数；
26 
27     while(i--)
28     {
29     cin>>N>>M;
30     if(M==1)
31     {
32         cout<<1<<endl;
33         continue;
34     }
35     if(N<M)
36     {
37         cout<<"Wrong Input!"<<endl;
38         continue;
39     }
40     else
41     {
42     m=D(M);
43     n=C(N,M);
44     if(N==M)
45         cout<<m<<endl;
46     else 
47         cout<<m*n<<endl;
48     }
49     } 
50     return 0;
51 }