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

Problem Description

國(guó)慶期間,省城HZ剛剛舉行了一場(chǎng)盛大的集體婚禮,為了使婚禮進(jìn)行的豐富一些,司儀臨時(shí)想出了有一個(gè)有意思的節(jié)目,叫做"考新郎",具體的操作是這樣的:

首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭隨機(jī)坐成一排;
然后,讓各位新郎尋找自己的新娘.每人只準(zhǔn)找一個(gè),并且不允許多人找一個(gè).
最后,揭開蓋頭,如果找錯(cuò)了對(duì)象就要當(dāng)眾跪搓衣板...
看來(lái)做新郎也不是容易的事情...
假設(shè)一共有N對(duì)新婚夫婦,其中有M個(gè)新郎找錯(cuò)了新娘,求發(fā)生這種情況一共有多少種可能.

Input

輸入數(shù)據(jù)的第一行是一個(gè)整數(shù)C,表示測(cè)試實(shí)例的個(gè)數(shù)，然后是C行數(shù)據(jù)，每行包含兩個(gè)整數(shù)N和M(1<M<=N<=20)。

Output

對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出一共有多少種發(fā)生這種情況的可能，每個(gè)實(shí)例的輸出占一行。

Sample Input

2 2 2 3 2

Sample Output

1 3

解題思路：

錯(cuò)排+組合

錯(cuò)排公式 f(n)=(n-1)*[f(n-1)+f(n-2)]

首先考慮，如果開始有n-1個(gè)新郎，并且這n-1個(gè)人都已經(jīng)完成了錯(cuò)排（有f(n-1)種可能），

現(xiàn)在又來(lái)了一個(gè)人，那么后來(lái)的第n個(gè)人可以通過(guò)用自己的新娘去和那n-1個(gè)人中的任意一個(gè)

交換，來(lái)實(shí)現(xiàn)n個(gè)人都錯(cuò)排。這種情況有(n-1)*f[n-1]種可能;

另外，如果開始的n-1個(gè)人不是都錯(cuò)排，那么要想使第n個(gè)人過(guò)來(lái)與其中一個(gè)交換后實(shí)現(xiàn)錯(cuò)排的話就必須滿足兩個(gè)條件：

1.那n-1個(gè)人中只有一個(gè)人選到了自己的新娘，也就是說(shuō)有n-2個(gè)人都已經(jīng)錯(cuò)排了。

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

其他情況都不能滿足n個(gè)人錯(cuò)排。

因此遞推關(guān)系：f[n]=(n-1)*(f[n-1]+f[n-2])。

代碼：

#include<stdio.h>
long long f[30];
long long jc(long long a)//求階乘
{
    if(a==1)
        return 1;
    else
        return a*jc(a-1);
}
 
long long C(long long n,long long m)//求組合數(shù)
{
    if(m==0||m==n)return 1;
    long long a,b,c;
    a=jc(n);
    b=jc(m);
    c=jc(n-m);
    return a/c/b;
}
 
int main()
{
    f[0]=0;f[1]=0;f[2]=1;
 
    for(int i=3;i<=20;i++)
        f[i]=(i-1)*(f[i-1]+f[i-2]);
    long long n,m;
    int c;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d %d",&n,&m);
        printf("%d\n",C(n,m)*f[m]);
    }
    return 0;
}