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

2019-11-14 13:06:47

字體：大中小

供稿：網(wǎng)友

國慶期間,省城HZ剛剛舉行了一場盛大的集體婚礼,為了使婚礼進行的豐富一些,司儀臨時想出了有一個有意思的節(jié)目,叫做"考新郎",具體的操作是這樣的:

首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭隨機坐成一排;然后,讓各位新郎尋找自己的新娘.每人只準找一個,并且不允許多人找一個.最后,揭開蓋頭,如果找錯了對象就要當眾跪搓衣板...看來做新郎也不是容易的事情...假設一共有N對新婚夫婦,其中有M個新郎找錯了新娘,求發(fā)生這種情況一共有多少種可能. Input輸入數(shù)據(jù)的第一行是一個整數(shù)C,表示測試實例的個數(shù)，然后是C行數(shù)據(jù)，每行包含兩個整數(shù)N和M(1<M<=N<=20)。 Output對于每個測試實例，請輸出一共有多少種發(fā)生這種情況的可能，每個實例的輸出占一行。 Sample Input

22 23 2 Sample Output13
根據(jù)題目的描述，可以看出根據(jù)排列組合與錯排求出遞推公式。
錯排公式:f(n)=(n-1)*(f(n-1)+f(n-2))
排列組合數(shù)乘以錯排結果就可以。
關于錯排：http://blog.csdn.net/aianswer3/article/details/54860993
AC代碼：
#include <stdio.h>#include <stdlib.h>int main(){    int t,n,m,i;    long long fact[30],num[30];    scanf("%d",&t);    num[1]=0;num[2]=1;    fact[0]=1;fact[1]=1;fact[2]=2;    for(i=3;i<25;i++)    {        num[i]=(i-1)*(num[i-1]+num[i-2]);    }    for(i=3;i<25;i++)    {        fact[i]=fact[i-1]*i;    }    while(t--)    {        scanf("%d%d",&n,&m);        PRintf("%lld/n",num[m]*(fact[n]/fact[m]/fact[n-m]));    }    return 0;}