记录编号	303648	评测结果	AAAAA
题目名称	[NOI 1999]钉子和小球	最终得分	100
用户昵称	安呐一条小咸鱼。	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2016-09-06 10:24:17	内存使用	13.02 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
int cnt=0;bool flag=0;
class CBigInt{
	private:
		int m_num[1100];
		int len;
	public:
		CBigInt()
		{
			memset(m_num,0,sizeof(m_num));
			len=1;
		}
		CBigInt(const char *ch)
		{
			memset(m_num,0,sizeof(m_num));
			len=strlen(ch);
			for(int i=0;i<len;i++)
			{
				m_num[len-i-1]=ch[i]-'0';
			}
		}
		CBigInt operator +(const CBigInt& x)const
		{
			CBigInt ret;
			int l=max(len,x.len);
			ret.len=l;
			for(int i=0;i<l;i++)
			{
				ret.m_num[i]+=m_num[i]+x.m_num[i];
				if(ret.m_num[i]>=10)
				{
					ret.m_num[i+1]=1;
					ret.m_num[i]-=10;
				}
			}
			if(ret.m_num[l]!=0)ret.len=l+1;
			return ret;
		}
		CBigInt operator -(const CBigInt& x)const
		{
			CBigInt ret;
			int id,d=0;
			for(id=0;id<len;id++)
			{
				d=m_num[id]+d;
				if(d>=x.m_num[id])
				{
					ret.m_num[id]=d-x.m_num[id];
					d=0;
				}
				else
				{
					ret.m_num[id]=d+10-x.m_num[id];
					d=-1;
				}
			}
			id=len-1;
			while(id>0&&ret.m_num[id]==0)id--;
			ret.len=id+1;
			return ret;
		}
		bool operator ==(const CBigInt &x)
		{
			if(len!=x.len)return false;
			int id=len;
			while(id>=0)
			{
				if(m_num[id]!=x.m_num[id])return false;
				--id;
			}
			return true;
		}
		bool operator !=(const CBigInt &x)
		{
			if(len!=x.len)return true;
			int id=len;
			while(id>=0)
			{
				if(m_num[id]!=x.m_num[id])return true;
				--id;
			}
			return false;
		}
		CBigInt operator *(const CBigInt& x)const
		{
			CBigInt ret;
			int i,j;
			ret.len=len+x.len-1;
			for(i=0;i<len;i++)
			{
				for(int j=0;j<x.len;j++)
				{
					ret.m_num[i+j]+=m_num[i]*x.m_num[j];
					if(ret.m_num[i+j]>=10)
					{
						ret.m_num[i+j+1]+=ret.m_num[i+j]/10;
						ret.m_num[i+j]%=10;
					}
				}
			}
			if(ret.m_num[ret.len]!=0)ret.len+=1;
			return ret;
		}
		CBigInt operator /(const int &x)
		{
			CBigInt ret;
			int d=0,id=len-1;
			while(id>=0)
			{
				d=m_num[id]+d*10;
				ret.m_num[id]=d/x;
				d=d%x;
				id--;
			}
			id=len-1;
			while(id>0&&ret.m_num[id]==0)--id;
			ret.len=id+1;
			return ret;
		}
		void print()const
		{
			for(int i=len-1;i>=0;--i)printf("%d",m_num[i]);
		}
};
char G[51][51];
int n,m;
using namespace std;
void Init()
{
	char ch;
	int I,J;
	scanf("%d %d",&n,&m);
	for(I=1;I<=n;I++)
	 for(J=0;J<=I-1;J++)
	  cin>>ch,G[I][J]=ch;
}
CBigInt P[55][55];
CBigInt tot("1");
void Print()
{
	CBigInt u,v;
	CBigInt cmp("0");
	if(P[n+1][m]==cmp)v=("0"),u=("1");
	else {
		v=P[n+1][m];
		u=tot;
		while(v/2!=( v- ("1") )/2&&u/2!=(u-("1"))/2)
		 v=v/2,u=u/2;
	}
	v.print();printf("/");u.print();
}
int main()
{
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout);
	Init();	
	int i,j;
	for(i=1;i<=n;i++)tot=tot*("2");
	P[1][0]=tot;
	for(i=1;i<=n;i++)
	{
	 for(j=0;j<=i-1;j++)
	 {
	   if(G[i][j]=='*')
	   {
	   	 P[i+1][j]=P[i+1][j]+P[i][j]/2;
	     P[i+1][j+1]=P[i+1][j+1]+P[i][j]/2;
	   }
	   else
	   {
	     P[i+2][j+1]=P[i+2][j+1]+P[i][j];
	   }
	 }	  
	}
	Print();
}