有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。
让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。
我们知道小球落在第i个格子中的概率pi= 
，其中i为格子的编号，从左至右依次为0,1,...,n。
现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。
输入
第1行为整数n（2<=n<=50）和m（0<=m<=n）。以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。
输出
仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概pm。既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。
样例输入
5 2** .* * ** . * * * * * * *
样例输出
7/16 ***********************************************************************************
一道简单的递推题，在做事特别注意的是数据类型的处理long long;
**********************************************************************************
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #define LL long long 6 using namespace std; 7 LL n,m,i,j; 8 LL dp[1000][1000],temp;//变量常量说明 9 char a[1000][1000];//变量常量说明 10 char ch;//变量常量说明 11 LL zide(LL a,LL b)//求最大公约数的函数 12 { 13 if(b==0) 14 return a; 15 return zide(b,a%b); 16 } 17 void init()//初始化函数 18 { 19 cin>>n>>m; 20 for(i=0;i<n;i++) 21 { 22 j=0; 23 while(1)//输入有技巧 24 { 25 ch=getchar(); 26 if(ch=='*'||ch=='.') 27 a[i][j++]=ch; 28 if(j>i)break; 29 } 30 } 31 32 33 } 34 void sovle()//递推函数 35 { 36 memset(dp,0,sizeof(dp)); 37 dp[0][0]=(LL)((LL)1<<(LL)n);//注意此此处要强制转换LL 38 //cout<<dp[0][0]<<endl; 39 for(i=1;i<=n;i++) 40 for(j=0;j<i;j++) 41 { 42 if(a[i-1][j]=='*')//如果有钉子，下面的两个钉子各分这个钉子的一半小球 43 { 44 temp=dp[i-1][j]>>1; 45 // cout<<temp<<endl; 46 dp[i][j]+=temp; 47 dp[i][j+1]+=temp; 48 //cout<<dp[i][j]<<' '<<dp[i][j+1]<<endl; 49 } 50 else 51 if(a[i-1][j]=='.')//如果无钉子，则直接落到隔一行正对的钉子上 52 dp[i+1][j+1]+=dp[i-1][j]; 53 //cout<<dp[i+1][j+1]<<endl; 54 } 55 LL d=zide(dp[0][0],dp[n][m]); 56 //cout<<d<<endl; 57 cout<<dp[n][m]/d<<'/'<<dp[0][0]/d<<endl;//输出结果 58 59 } 60 61 int main() 62 { 63 freopen("ball.in","r",stdin); 64 freopen("ball.out","w",stdout); 65 66 init(); 67 sovle(); 68 return 0; 69 }
