http://poj.org/problem?id=1189

Description

有一個三角形木板,豎直立放。上面釘著n(n+1)/2顆釘子，還有(n+1)個格子（當n=5時如圖1）。每顆釘子和周圍的釘子的距離都等于d，每一個格子的寬度也都等于d，且除了最左端和最右端的格子外每一個格子都正對著最以下一排釘子的間隙。?
讓一個直徑略小于d的小球中心正對著最上面的釘子在板上自由滾落，小球每碰到一個釘子都可能落向左邊或右邊（概率各1/2）。且球的中心還會正對著下一顆將要碰上的釘子。比如圖2就是小球一條可能的路徑。?
我們知道小球落在第i個格子中的概率pi=pi=，當中i為格子的編號，從左至右依次為0,1,...,n。?
如今的問題是計算拔掉某些釘子后，小球落在編號為m的格子中的概率pm。

假定最以下一排釘子不會被拔掉。比如圖3是某些釘子被拔掉后小球一條可能的路徑。?

Input

Output

Sample Input

5 2
** .* * ** . * *
* * * * *

Sample Output

7/16

對于每個沒有挖掉的釘子(i,j)：dp[i+1][j]+=dp[i][j]/2; dp[i+1][j+1]+=dp[i][j]/2; 對于挖掉的釘子(i,j)：dp[i+2][j+1]+=dp[i][j]; */ #include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; bool a[2555]; int n,m; LL dp[55][55]; LL gcd(LL x,LL y) { if(y==0)return x; return gcd(y,x%y); } int main() { while(~scanf("%d%d",&n,&m)) { int k=1; for(int i=1; i<=n; i++) { for(int j=1; j<=i; j++) { char str[12]; scanf("%s",str); if(str[0]=='*') { a[k++]=true; } else { a[k++]=false; } //printf("%d\n",a[k-1]); } //puts(""); } memset(dp,0,sizeof(dp)); dp[1][1]=1LL<<n; for(int i=1; i<=n; i++) { int x=i*(i-1)/2; for(int j=1; j<=i; j++) { if(a[j+x]) { dp[i+1][j]+=dp[i][j]/2; dp[i+1][j+1]+=dp[i][j]/2; } else { dp[i+2][j+1]+=dp[i][j]; } } } LL x=1LL<<n; LL y=dp[n+1][m+1]; LL g=gcd(x,y); printf("%lld/%lld\n",y/g,x/g); } return 0; }