不容易系列之(4)——考新郎 Time Limit: 2000/1000 MS (java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 35528 Accepted Submission(s): 13007

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

這道題考察的和hdu2048 差不多，都是錯(cuò)排問題，不過hdu2048是全錯(cuò)排。 具體思路如下： 在n個(gè)新郎里，隨機(jī)選m個(gè)。就是m！（n-m）！/n!種方案。 對(duì)著m個(gè)新郎進(jìn)行全錯(cuò)排。D[n]=D[n-1]+D[n-2], D[1]=0, D[2]=1。 錯(cuò)排具體推到請(qǐng)看錯(cuò)排推導(dǎo)以及hdu2048解析

AC代碼：