记录编号	59258	评测结果	AAAAA
题目名称	[NOI 1999]钉子和小球	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2013-05-05 10:52:18	内存使用	0.37 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long Euclid(long long x,long long y){
	return y==0?x:Euclid(y,x%y);
}
class FRAC{
public:
	long long a,b;//分子/分母
	FRAC(){a=b=1;}
	void output(void){cout<<a<<"/"<<b;}
	void simp(void){
		long long g=Euclid(a,b);
		a/=g,b/=g;
	}
};
bool operator < (FRAC x,FRAC y){
	return x.a*y.b<x.b*y.a;
}
bool operator > (FRAC x,FRAC y){
	return x.a*y.b>x.b*y.a;
}
bool operator != (FRAC x,FRAC y){
	return x.a*y.b!=x.b*y.a;
}
bool operator == (FRAC x,FRAC y){
	return x.a*y.b==x.b*y.a;
}
FRAC operator * (FRAC x,FRAC y){
	x.a*=y.a,x.b*=y.b;
	x.simp();
	return x;
}
FRAC operator / (FRAC x,FRAC y){
	x.a*=y.b,x.b*=y.a;
	x.simp();
	return x;
}
FRAC operator + (FRAC x,FRAC y){
	long long lcm=Euclid(x.b,y.b);
	lcm=x.b/lcm*y.b;
	FRAC ans;
	ans.b=lcm;
	ans.a=x.a*(lcm/x.b)+y.a*(lcm/y.b);
	ans.simp();
	return ans;
}
FRAC operator - (FRAC x,FRAC y){
	FRAC temp;
	temp.b=x.b*y.b;
	temp.a=x.a*y.b-x.b*y.a;
	temp.simp();
	return temp;
}
FRAC operator * (FRAC x,long long y){
	x.a*=y;
	x.simp();
	return x;
}
FRAC operator / (FRAC x,long long y){
	x.b*=y;
	x.simp();
	return x;
}
const int SIZEN=60;
int n,m;//n是规模,m是目标
//下标是1~n
FRAC p[SIZEN][SIZEN];
char board[SIZEN][SIZEN];
void read(void){
	int i,j;
	char ch;
	scanf("%d%d",&n,&m);
	FRAC one;one.a=one.b=1;
	FRAC zero;zero.a=0,zero.b=1;
	p[1][1]=one;
	for(i=2;i<=n+1;i++){
		for(j=1;j<=i;j++) p[i][j]=zero;
	}
	for(i=1;i<=n;i++){
		j=1;
		while(1){
			ch=getchar();
			if(ch=='*'||ch=='.') board[i][j++]=ch;
			if(j>i) break;
		}
	}
}
void work(void){
	int i,j;
	FRAC temp;
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			if(board[i][j]=='*'){//有钉子
				temp=p[i][j];
				temp=temp/2;
				p[i+1][j]=p[i+1][j]+temp;
				p[i+1][j+1]=p[i+1][j+1]+temp;
			}
			else{//无钉子
				p[i+2][j+1]=p[i+2][j+1]+p[i][j];
			}
		}
	}
	p[n+1][m+1].output();
}
int main(){
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	read();
	work();
	return 0;
}