POJ 1189 钉子和小球 思路+疑惑
题目链接：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 longllong 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啊！
求哪位大牛能指出啊？！