4860255_wa.cpp

部分PKU上的源码

#include<iostream>
using namespace std;
int getgong(int x,int y)
{
	int t;
	if(x<y) {t=y;y=x;x=t;}
	if(y==0) return 1;
	while(x%y!=0)
	{
		int t1=x%y;
		x=y;y=t1;
		if(y==0) return 1;
	}
	return y;
}
struct fs
{
	int fz,fm;
};
fs x[60][60];
fs add(fs a,fs b)
{
	fs re;
	re.fz=a.fm*b.fz+a.fz*b.fm;
	re.fm=a.fm*b.fm;
	int t=getgong(re.fz,re.fm);
	re.fz/=t;
	re.fm/=t;
	return re;
}
fs did(fs a)
{
	if(a.fz%2==0) a.fz/=2;
	else a.fm*=2;
	return a;
}
int main()
{
	int n,m,i,j;
	cin>>n>>m;
	fs temp,ling;
	temp.fz=1;temp.fm=1;
	ling.fz=0;ling.fm=1;
	for(i=1;i<=55;i++)
		for(j=1;j<=i+1;j++) x[i][j]=ling;
	x[0][1]=temp;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			char in;
			cin>>in;
			if(in=='*')
			{
				fs t=did(x[i-1][j]);
				fs t2=add(x[i][j],t);
				x[i][j]=t2;
				t2=add(x[i][j+1],t);
				x[i][j+1]=t2;
			}
			else
			{
				fs t=add(x[i+1][j+1],x[i-1][j]);
				x[i+1][j+1]=t;
			}
		}
	}
	cout<<x[n][m+1].fz<<"/"<<x[n][m+1].fm<<endl;
	return 0;
}