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

分析：這個道題就是求N中有多少中M個數的錯排。

是以先找到N個新郎中M個錯一共有幾種，顯然是CMN=N!/(M!*(N-M)!)。即CMN=N!/M!/(N-M)!。

然後在求出M個數的錯排個數，遞推關系：f[n]=(n-1)*(f[n-1]+f[n-2])

詳細推導過程：

錯排的情況：

首先考慮，如果開始有n-1個新郎，并且這n-1個人都已經完成了錯排（有f(n-1)種可能），現在又來了一個人，那麼後來的第n個人可以通過用自己的新娘去和那n-1個人中的任意一個交換，來實作n個人都錯排。這種情況有(n-1)*f[n-1]種可能;

另外，如果開始的n-1個人不是都錯排，那麼要想使第n個人過來與其中一個交換後實作錯排的話就必須滿足兩個條件：

1.那n-1個人中隻有一個人選到了自己的新娘，也就是說有n-2個人都已經錯排了。

2.第n個人必須和那個選到自己新娘的人去交換，但那個選到自己新娘的人可以是n-1個人中的任意一個。這種情況有(n-1)*f[n-2]種可能。

其他情況都不能滿足n個人錯排。

是以遞推關系：f[n]=(n-1)*(f[n-1]+f[n-2])。

AC code:

#include <iostream>

using namespace std;

int main()

{

    int T,n,m,i;

    long long a[25],b[25];

    a[0] = 1; a[1] = 1,a[2] = 2;

    for(i = 3; i < 21;i++)

        a[i] = a[i-1]*i;

    b[0] = 0;b[1] = 1;b[2] = 1,b[3] = 2;

    for(i = 4; i < 21;i++)

        b[i] = (i-1)*(b[i-1]+b[i-2]);

    cin>>T;

    while(T--)

    {

        cin>>n>>m;

        cout<<a[n]/a[m]/a[n-m]*b[m]<<endl;

    }

    return 0;

}