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

2019-11-14 13:06:47

字體：大中小

供稿：網(wǎng)友

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

首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭隨機(jī)坐成一排;然后,讓各位新郎尋找自己的新娘.每人只準(zhǔn)找一個(gè),并且不允許多人找一個(gè).最后,揭開(kāi)蓋頭,如果找錯(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

22 23 2 Sample Output13
根據(jù)題目的描述，可以看出根據(jù)排列組合與錯(cuò)排求出遞推公式。
錯(cuò)排公式:f(n)=(n-1)*(f(n-1)+f(n-2))
排列組合數(shù)乘以錯(cuò)排結(jié)果就可以。
關(guān)于錯(cuò)排：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;}