Eva

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 1198  Solved: 466
Description

第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

/**************************************************************

    Problem: 1867

    User: ictsing

    Language: C++

    Result: Accepted

    Time:8 ms

    Memory:1352 kb

****************************************************************/

 

//1867: [Noi1999]钉子和小球

/*

f[i][j]代表小球落到第i行第j个格子上的概率，

那么f[i+1][j]=(1/2)*f[i][j],

   f[i+1][j+1]=(1/2)*f[i][j](a[i][j]=1)

   f[1][1]=1;

分数约分可能爆ll,所以gcd一下

*/

#include <iostream>

#include <cstdio>

#include <cstdio>

using namespace std;

const int mt = 50+10;

typedef long long ll;

ll gcd(ll a,ll b)

{

    if(!b) return a;

    return gcd(b,a%b);

}

struct fra

{

    ll up,dn;

    void reduc()

    {

        ll t=gcd(up,dn);

        up/=t,dn/=t;

    }

}f[mt][mt];

fra operator * (fra a,fra b)

{

    fra c;

    c.up=a.up*b.up;

    c.dn=a.dn*b.dn;

    c.reduc();

    return c;

}

fra operator + (fra a,fra b)

{

    ll t=gcd(a.dn,b.dn);

    fra c;

    c.up=b.dn/t*a.up+a.dn/t*b.up;

    c.dn=a.dn/t*b.dn;

    c.reduc();

    return c;

}

char map[mt][mt];

int n,m;

char getch()

{

    char ch=getchar();

    while(ch==' '||ch=='\n'||ch=='\r'||ch=='\t') ch=getchar();

    return ch;

}

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{

 

    int n=read(),m=read();

    for(int i=1;i<=n;i++)

        for(int j=1;j<=i;j++)

            map[i][j]=getch();

    /*for(int i=1;i<=n;i++)

        for(int j=1;j<=i;j++)

            cout<<map[i][j]<<endl;*/

    for(int i=1;i<=n+2;i++)

        for(int j=1;j<=n+2;j++)

            f[i][j].up=0,f[i][j].dn=1;//关于分数一定要全部+边界初始化的时候全部搞成0/1不然各种烦人

    fra ma;

    ma.up=1,ma.dn=2;

    f[1][1].up=1,f[1][1].dn=1;

 

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

        {

            //cout<<i<<j<<endl;

            if(map[i][j]=='*')

            {

                //cout<<f[i][j].up<<" "<<f[i][j].dn<<endl;

                //cout<<ma.up<<" "<<ma.dn<<endl;

                //fra c=ma*f[j][j];

                //cout<<c.up<<" "<<c.dn<<endl;

                //c=c+f[i+1][j];

                //cout<<c.up<<" "<<

                f[i+1][j]=f[i+1][j]+f[i][j]*ma;

                f[i+1][j+1]=f[i+1][j+1]+f[i][j]*ma;

                //cout<<f[i+1][j].up<<"/"<<f[i+1][j].dn<<endl;

                //cout<<f[i+1][j+1].up<<"//"<<f[i+1][j+1].dn<<endl;

            }

            else 

            {

                //cout<<f[i+2][j+1].up<<" *** "<<f[i+2][j+1].dn<<endl;

                f[i+2][j+1]=f[i+2][j+1]+f[i][j];

                //cout<<f[i+2][j+1].up<<"///"<<f[i+2][j+1].dn<<endl;

            }

        }

    cout<<f[n+1][m+1].up<<"/"<<f[n+1][m+1].dn;

    //printf("%lld/%lld",f[n+1][m+1].up,f[n+1][m+1].dn);

    return 0;

}

/*

5 2

     *

    * .

   * * *

  * . * *

 * * * * *

*/