学步园

假设F(a,b,c)表示在当前拥有ABC/的数量分别为abc，那么F(a,b,c)=F(a-1,b,c)+F(a,b-1,c)+F(a,b,c-1)。

看上去很简单，实际上的操作有两个难点。

1. F(a,b,c)相当大。采用高精度加法。

2.a的取值范围相当大。只能使用char数组。

#include <cstdio>
#include <string>

int N;
char f[61][61][61][90];

void dp ();
void print ( int, int, int );

int main ()
...{
    //freopen ( "in.txt", "r", stdin );
    dp ();
    while ( scanf ( "%d", &N ) == 1 )
    ...{
        //printf ( "%0.0f ", f[N][N][N] );
        print ( N, N, N );
        printf ( " " );
    }
    return 0;
}

void print ( int a, int b, int c )
...{
    int i;
    for ( i = 89; i >= 0; i -- )
    ...{
        if ( f[a][b][c][i] )
            break;
    }
    if ( i == -1 )
        printf ( "0 " );
    else
    ...{
        for ( ; i >= 0; i -- )
            printf ( "%d", f[a][b][c][i] );
        printf ( " " );
    }
}

void dp ()
...{
    int a, b, c, l, i, ac = 0;
    memset ( f, 0, sizeof ( f ) );
    f[1][0][0][0] = 1;
    for ( l = 2; l <= 180; l ++ )
    ...{
        for ( a = 0; a <= l && a <= 60; a ++ )
        ...{
            for ( b = 0; b <= a && b <= 60; b ++ )
            ...{
                c = l - a - b;
                if ( c > b )
                    continue;
                if ( c < 0 )
                    break;
                if ( a > 0 )
                ...{
                    //f[a][b][c] += f[a - 1][b][c];        
                    ac = 0;
                    for ( i = 0; i < 90; i ++ )
                    ...{
                        f[a][b][c][i] += f[a - 1][b][c][i] + ac;
                        if ( f[a][b][c][i] >= 10 )
                            ac = 1, f[a][b][c][i] -= 10;
                        else 
                            ac = 0;
                    }                    
                }
                if ( b > 0 )
                ...{
                    //f[a][b][c] += f[a][b - 1][c];    
                    ac = 0;
                    for ( i = 0; i < 90; i ++ )
                    ...{
                        f[a][b][c][i] += f[a][b - 1][c][i] + ac;
                        if ( f[a][b][c][i] >= 10 )
                            ac = 1, f[a][b][c][i] -= 10;
                        else 
                            ac = 0;
                    }
                }
                if ( c > 0 )
                ...{
                    //f[a][b][c] += f[a][b][c - 1];
                    ac = 0;
                    for ( i = 0; i < 90; i ++ )
                    ...{
                        f[a][b][c][i] += f[a][b][c - 1][i] + ac;
                        if ( f[a][b][c][i] >= 10 )
                            ac = 1, f[a][b][c][i] -= 10;
                        else
                            ac = 0;
                    }
                }
            }
        }
    }
}