题目链接：http://poj.org/problem?id=1189
这题我是这么思考的，将钉子和它左右可以钻过小球的地方都看成空格，那么其实一行的空格数就是2*i+1,i为那行的钉子数。如果有3个钉子，那么要看成7个空格。
和很多人的思路可能不同，我觉得该行的可能性可以先照抄上面一行的（当然位置要调整），然后如果该点是钉子的话，将它的可能行平分给左右的空格，所以每行是钉子地方的可能行都是0，这样也就能覆盖把钉子拔出，小球直接落下的情况，因为一开始我们就复制了上一行的可能性。下面上代码：
#include<iostream>
#include<algorithm>
#include<sstream>
#include<cmath>
using namespace std;
#define llong long long
llong maxCommon(llong a,llong b)
{
return a%b==0?b:(maxCommon(b,a%b));
};
const llong N=110;
llong dp[N][N];
char input[N][N];
int main()
{
for(llong i=0;i<N;i++)
for(llong j=0;j<N;j++)
dp[i][j]=0;
llong n,m;
cin>>n>>m;
for(llong i=1;i<=n;i++)
for(llong j=1;j<=i;j++)
cin>>input[i][j];
llong sum=1;
sum<<=n;
if(input[1][1]=='*')
{
dp[1][1]=sum/2;
dp[1][2]=0;
dp[1][3]=sum/2;
}
else
{
dp[1][1]=0;
dp[1][2]=sum;
dp[1][3]=0;
}
for(llong i=2;i<=n;i++)
{
dp[i][0]=0;
llong j=1;
for(;j<=2*i;j++)
dp[i][j]=dp[i-1][j-1];
dp[i][j]=0;
for(llong k=2;k<=2*i;k+=2)
{
if(input[i][k/2]=='*')
{
dp[i][k-1]+=dp[i][k]/2;
dp[i][k+1]+=dp[i][k]/2;
dp[i][k]=0;
}
}
}
llong result=dp[n][2*m+1];
llong common=maxCommon(1<<n,result);
if(result==0)
cout<<"0/1"<<endl;
else
cout<<result/common<<"/"<<sum/common<<endl;
return 0;
}
POJ上面的易错的数据都已经测试过，例如：
5 2
.
* .
* . *
* * * *
* * * * *
1/2
6 3
.
* *
* . *
* * * *
* * . * *
* * * * * *
1/1
#1)( 答案是710466673 / 4294967296 ) 33 16 * ** *** **** ***** ****** ******* ******** ********* ********** *********** **.**.**.*** ******.****** *****.******** ****.****.***** ******.********* ***.*.****.****** *****.*****.****** ***.*****.***.***** ***********.******** *********.*********** ********************** ********.************** ******.***.************* *********.**.************ **********.*************** ********.***************.** ***********************.**** ***********************.***** ***************.************** **************.**************** ******************************** *********************************
#2)(答案是5723285335 / 34359738368) 35 16 * ** *** **** ***** ****** ******* ******** ********* **.******* *********** **.**.**.*** ******.****** *****.******** ****.****.***** ******.********* ***.*.****.****** *****.*****.****** ***.*****.***.***** ***********.******** *********.*********** ********************** ********.************** ******.***.************* *********.**.************ **********.*************** ********.***************.** ***********************.**** ***********************.***** ***************.************** **************.**************** *******..*********************** **********.***..***************** *************.***..*************** ***********************************
数据都测试过了呀！！！！！！！！
但是一直木有accept啊！
求哪位大牛能指出啊？！