学步园

下午搞了五道菜题，还看了一场冠军杯录播，生活真充实。

此题相对而言稍嫌繁琐。排列组合的题目，大致上从小到大顺推即可。设b[i][j]中i表示字符串长度，j表示字符串中用到的字母个数，不难推出b[i][j] = b[i-1][j-1] + b[i - 1][j] * j。

当题目无法变得更难的时候，出题者就会使出高精度加法。事实上，这也只不过多打几行而已……

#include <cstdio>
#include <string>

int b[51][51][50], N;

void add ( int i, int j )
...{
    int k;
    for ( k = 0; k < 50; k ++ )
        b[i][j][k] = b[i - 1][j - 1][k] + b[i - 1][j][k] * j;
    int c = 0, t;
    for ( k = 0; k < 50; k ++ )
    ...{
        t = b[i][j][k] + c;
        c = t / 10;
        b[i][j][k] = t % 10;
    }
}

void dp ()
...{
    memset ( b, 0x00, sizeof ( b ) );
    int i, j;
    for ( i = 1; i <= 50; i ++ )
    ...{
        b[i][1][0] = b[i][i][0] = 1;
    }
    for ( i = 3; i <= 50; i ++ )
    ...{
        for ( j = 2; j < i; j ++ )
        ...{
            add ( i, j );
        }
    }
}

void print ( int i, int j )
...{
    int k;
    for ( k = 49; k >= 0; k -- )
        if ( b[i][j][k] )
            break;
    if ( k == -1 )
        printf ( "0" );
    for ( ; k >= 0; k -- )
        printf ( "%d", b[i][j][k] );
    printf ( " " );
}

void print ( int n )
...{
    printf ( "%d ", n );
    int i, j, k;
    int ans[50];
    memset ( ans, 0, sizeof ( ans ) );
    for ( i = 1; i <= n; i ++ )
    ...{
        for ( j = 0; j < 50; j ++ )
        ...{
            ans[j] += b[n][i][j];
        }
    }
    int t, c = 0;
    for ( k = 0; k < 50; k ++ )
    ...{
        t = ans[k] + c;
        c = t / 10;
        ans[k] = t % 10;
    }
    for ( k = 49; k >= 0; k -- )
        if ( ans[k] )
            break;
    if ( k == -1 )
        printf ( "0" );
    for ( ; k >= 0; k -- )
        printf ( "%d", ans[k] );
    printf ( " " );
}

int main ()
...{
    //freopen ( "in.txt", "r", stdin );
    dp ();
    //print ( 5, 2 );
    while ( scanf ( "%d", &N ) && N )
    ...{
        print ( N );
    }
    return 0;
}