xtu oj 1522 格子

发布时间:2024年01月13日

题目描述

一个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。利用剩余格子计算即可,放一个棋子消去棋子所在的行和列,下一个棋子在剩余棋子中填就行。注意考虑重复的情况。

文章来源:https://blog.csdn.net/m0_75005390/article/details/135575774
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。