第i层有2*i+1种可能的位置（从第1个空位到最后一个空位总共i+1个和i个钉子位置），用d[i][j]表示第i行在第j个位置掉落的概率的分子（分母是2^i）。
如果位置是空位，那么有3种情况：
(1).从上一个同样的位置掉落下来，
(2).掉落到左边的钉子（如果有）并向右走，
(3).掉落到右边的钉子（如果有）并向左走。
如果位置是有钉子的，有2种情况：
(1).这个位置有钉子，那么不可能以这个位置掉落，，
(2).这个位置没有钉子，可以从上一个同样的位置掉落下来。
#include<stdio.h>#include<stdlib.h>#include<string.h>typedef long long LL;int a[110][110];LL d[110][210];char e[1100];int main(void){int i,j,n,m,top,lo;LL p,q,sump;scanf("%d%d",&n,&m);while(getchar()==' '){;}for(i=1;i<=n;i++){gets(e);lo=strlen(e);top=0;for(j=0;j<lo;j++){if(e[j]=='*'){top++;a[i][top]=1;}else if(e[j]=='.'){top++;a[i][top]=0;}}}if(a[1][1]==1){d[1][1]=d[1][3]=1;d[1][2]=0;}else{d[1][1]=d[1][3]=0;d[1][2]=2;}for(i=2;i<=n;i++){d[i][1]=(a[i][1]==1)?d[i-1][1]:0;d[i][2*i+1]=(a[i][i]==1)?d[i-1][2*i-1]:0;for(j=2;j<2*i+1;j++){if(j%2==1){sump=d[i-1][j-1]*2;sump=sump+((a[i][j/2]==1)?d[i-1][j-2]:0);sump=sump+((a[i][j/2+1]==1)?d[i-1][j]:0);}else{sump=(a[i][j/2]==1)?0:2*d[i-1][j-1];}d[i][j]=sump;}}if(q==0){printf("0/1\n");}else{p=d[n][2*m+1];q=(LL)1<<n;while((p%2==0)&&(q%2==0)){p=p/2;q=q/2;}printf("%lld/%lld\n",p,q);}return 0;}
没有伞的孩子必须努力奔跑!
