xtu oj 1522 格子

题目描述

一个n×m的网格，格子里最多能放一枚棋子，将k枚棋子随机放入不同的网格中，使得同行同列最多只有一枚棋子，请问概率是多少？

输入格式

第一行是一个整数T?(1≤T≤512)，表示样例的个数。

以后每行一个样例，为三个整数n,m,k,?(1≤n,m,k≤8)

输出格式

每行输出一个样例的结果，如果概率为0，输出0；如果概率为1，输出1；否则输出一个分数x/y，保证x与y互质。

样例输入

2
3 3 2
3 3 3

样例输出

1/2
1/14

AC代码

#include<stdio.h>
#define ll long long
ll gcd(ll a,ll b){
	ll t;
	while(a%b!=0){
		t=a%b;
		a=b;
		b=t;
	}
	return b;
}
//找最小值 
ll Min(ll a,ll b){
	if(a>b)return b;
	else return a;
}
//第一个棋子n*m种放法，第二个棋子n*m-1放法，以此类推 
ll Solve(ll m,ll n){
	ll i,res=1;
	for(i=m;i>=m-n+1;i--){
		res*=i;
	}
	return res;
}
int main(){
    int T;
	scanf("%d",&T);
	while(T--){
		int i;
		 ll n,m,k;
		 scanf("%I64d%I64d%I64d",&n,&m,&k);
		 ll min=Min(n,m);
		 if(k>min)printf("0\n");
		 else if(k==1)printf("1\n");
		 else{
		 	ll fm=Solve(n*m,k);
		    //放入棋子剩余的格子数 
		    ll grid=n*m;
		    ll fz=1;
		    for(i=1;i<=k;i++){
		      fz*=grid;
		      //有重复减去的，所以要加上重复减去的 
		 	  grid=grid-n-m+1+2*(i-1);
		    }
		    ll g=gcd(fz,fm);
		    fz/=g;
		    fm/=g;
		    printf("%I64d/%I64d\n",fz,fm);
		 }
	}	
}

解题思路:先考虑特殊情况，k=1时，概率为1；k大于min(n,m),概率为0。利用剩余格子计算即可，放一个棋子消去棋子所在的行和列，下一个棋子在剩余棋子中填就行。注意考虑重复的情况。