不容易系列之(4)——考新郎 杭電 acm 2049 Java

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

Problem Description

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

首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭随機坐成一排;

然後,讓各位新郎尋找自己的新娘.每人隻準找一個,并且不允許多人找一個.

最後,揭開蓋頭,如果找錯了對象就要當衆跪搓衣闆...

看來做新郎也不是容易的事情...

假設一共有N對新婚夫婦,其中有M個新郎找錯了新娘,求發生這種情況一共有多少種可能.

Input

輸入資料的第一行是一個整數C,表示測試執行個體的個數，然後是C行資料，每行包含兩個整數N和M(1<M<=N<=20)。

Output

對于每個測試執行個體，請輸出一共有多少種發生這種情況的可能，每個執行個體的輸出占一行。

Sample Input

2 

2 2 

3 2

Sample Output

1 

3

程式每次輸入一組資料第一行輸入N，第二行輸入M 

import java.util.Scanner;

/**
 * 
 * @author admin
 *	Problem Description
 *		國慶期間,省城HZ剛剛舉行了一場盛大的集體婚禮,為了使婚禮進行的豐富
 *		一些,司儀臨時想出了有一個有意思的節目,叫做"考新郎",具體的操作是這樣的:
 *		首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭随機坐成一排;
 *		後,讓各位新郎尋找自己的新娘.每人隻準找一個,并且不允許多人找一個.
 *		最後,揭開蓋頭,如果找錯了對象就要當衆跪搓衣闆...
 *
 *		看來做新郎也不是容易的事情...
 *
 *		假設一共有N對新婚夫婦,其中有M個新郎找錯了新娘,求發生這種情況一共有多少種可能.
 *	
 *	Input
 *		輸入資料的第一行是一個整數C,表示測試執行個體的個數，然後是C行資料，每行包含
 *		兩個整數N和M(1<M<=N<=20)。
 *	Output
 *		對于每個測試執行個體，請輸出一共有多少種發生這種情況的可能，每個執行個體的輸出占一行。
 *	Sample Input
 *		2 
 *		2 2 
 *		3 2
 *	Sample Output
 *		1 
 *		3
 *
 */
public class NotEasy4 {
	static int time=0;
	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=Integer.valueOf(input.nextLine());
		int m=Integer.valueOf(input.nextLine());
		input.close();
		int[] arr=new int[m];
		for (int i = 0; i < arr.length; i++) {
			arr[i]=i;
		}
		paiLie(arr, 0);
		System.out.println((computerCnm(n, n-m))*time);
	}
	//全排列
	public static void paiLie(int[] arr,int t)
	{
		if(t==arr.length)
		{
			if(isOk(arr))
			{
				time++;
			}
			return ;
		}
		for (int i = t; i < arr.length; i++) {
			chage(arr, i, t);
			paiLie(arr, t+1);
			chage(arr, i, t);
		}
	}
	//交換數組的不同下标的值
	public static void chage(int[] arr,int i,int j)
	{
		int t=arr[i];
		arr[i]=arr[j];
		arr[j]=t;
	}
	//判斷配對是否正确
	public static boolean isOk(int[] arr)
	{
		for (int i = 0; i < arr.length; i++) {
			if(arr[i]==i)
			{
				return false;
			}
		}
		return true;
	}
	//求c(p,q)
	public static int computerCnm(int p,int q)
	{
		int t1=1;
		int t2=1;
		for (int i = q; i >0; i--) {
			t1*=p;
			p--;
			t2*=q;
			q--;
		}
		return t1/t2;
	}

}