bzoj千题计划189：bzoj1867: [Noi1999]钉子和小球

#include<cstdio>
#include<iostream>

using namespace std;

typedef long long LL;

#define N 52

bool nail[N][N];

LL getgcd(LL a,LL b) { return !b ? a : getgcd(b,a%b); }

struct Fraction
{
    LL molecule,denominator;

    void operator = (int p)
    {
        molecule=p;
        denominator=1;
    }
    
    Fraction operator * (Fraction p)
    {
        Fraction c;
        c.molecule=molecule;
        c.denominator=denominator<<1;
        LL gcd=getgcd(c.molecule,c.denominator);
        c.molecule/=gcd;
        c.denominator/=gcd;
        return c;
    }
    
    void operator += (Fraction p)
    {
        if(!denominator) 
        {
            *this=p;
            return;
        }
        Fraction c;
        LL gcd=getgcd(denominator,p.denominator);
        c.denominator=denominator/gcd*p.denominator;
        c.molecule=c.denominator/denominator*molecule+c.denominator/p.denominator*p.molecule;
        *this=c;
    }
    
    bool have()
    {
        return denominator;
    }
    
    void print()
    {
        if(!molecule) denominator=1;
        cout<<molecule<<‘/‘<<denominator;
    }
    
}half;

Fraction dp[N][N];

char getc()
{
    char c;
    while(1)
    {
        c=getchar();
        if(c==‘*‘||c==‘.‘) return c;
    }
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    char c;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
        {
            c=getc();
            if(c==‘*‘) nail[i][j]=true;
        }
    dp[1][1]=1;
    for(int i=2;i<=n+1;++i)
        for(int j=1;j<=i;++j)
        {

            if(nail[i-1][j-1] && dp[i-1][j-1].have()) dp[i][j]+=dp[i-1][j-1]*half;
            if(nail[i-1][j] && dp[i-1][j].have()) dp[i][j]+=dp[i-1][j]*half;
            if(!nail[i-2][j-1] && dp[i-2][j-1].have()) dp[i][j]+=dp[i-2][j-1];
        }
    dp[n+1][m+1].print();
}