题目描述
一个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代码文章来源:https://www.toymoban.com/news/detail-811790.html
#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 fz=1;
ll t=1;
for(i=0;i<k;i++){
t=(n-i)*(m-i);
fz*=t;
}
ll g=gcd(fz,fm);
fz/=g;
fm/=g;
printf("%I64d/%I64d\n",fz,fm);
}
}
}
解题思路:第一个棋子情况n*m,消去所在行和列,第二个棋子情况(n-1)*(m-1),以此类推。
总数:第一个棋子n*m种放法,第二个棋子n*m-1放法,以此类推
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://www.toymoban.com/news/detail-811790.html
到了这里,关于xtu oj 1522 格子的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!