[BZOJ 1867][NOI 1999]釘と小球(DP水題)

タイトルリンク
http://www.lydsy.com/JudgeOnline/problem.php?id=1867
構想
小球がi行目j格子に落ちる確率をf[i][j]で表す.DP方程式が簡単に得られる
f[i+1][j]+=12 f[i][j],f[i+1][j+1]+=12 f[i][j],(i,j)は釘
f[i+2][j+1]+=f[i][j],(i,j)はスペース
f[1][1]=1
それから気持ち悪い点数構造体を書けばいいです.穴があることに注意してください.点数は通分時にlong longを爆発させる可能性があります.
コード#コード#

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 60

using namespace std;

typedef long long int LL;

LL gcd(LL a,LL b)
{
    if(!b) return a;
    return gcd(b,a%b);
}

struct Fraction
{
    LL up,dn;
    //Fraction(){ up=0,dn=1; } //!!!
    Fraction(LL _up=0,LL _dn=1):up(_up),dn(_dn){}
    void reduction()
    {
        LL t=gcd(up,dn);
        up/=t,dn/=t;
    }
    void print()
    {
        cout<<up<<'/'<<dn;
    }
}f[MAXN][MAXN];

Fraction operator*(Fraction a,Fraction b)
{
    Fraction c=Fraction(a.up*b.up,a.dn*b.dn);
    c.reduction();
    return c;
}

Fraction operator+(Fraction a,Fraction b)
{
    LL t=gcd(a.dn,b.dn);
    Fraction c=Fraction(b.dn/t*a.up+a.dn/t*b.up,a.dn/t*b.dn);
    c.reduction();
    return c;
}

int n,m;
char map[MAXN][MAXN];

char getch()
{
    char ch=getchar();
    while(ch==' '||ch=='
'||ch=='\r'||ch=='\t') ch=getchar();
    return ch;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            map[i][j]=getch();
    f[1][1]=Fraction(1,1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(map[i][j]=='*')
                f[i+1][j]=f[i+1][j]+f[i][j]*Fraction(1,2),f[i+1][j+1]=f[i+1][j+1]+f[i][j]*Fraction(1,2);
            else
                f[i+2][j+1]=f[i+2][j+1]+f[i][j];
        }
    f[n+1][m+1].print();
    return 0;
}