组合问题 contest4 的问题

2011/8/3 23:59:53

Description

有n 种颜色的球，每种颜色的球的个数有任意多个，从中取m个，问有多少种取法

Input

每行2个正整数 n,m(<=31) ，n=0,m=0结束.

Output

输出有多少种取法

Sample Input

2 2 3 3 0 0

Sample Output

3 10

#include<stdio.h>
long long m1[40],m2[40],n,m;
void gf(  )
{
    for( long long i = 0; i < 40; ++i )
        m1[i] = 0,m2[i] = 0;m1[0] = 1;
    for( long long i = 1; i <= n; ++i )
    {
        long long j;
        for(  j = 0; j <= m;++j )
            for( long long k = 0; k + j <= m; k += 1 )
                m2[j+k] += m1[j];
        for( j = 0; j <= m; ++j )
            m1[j] = m2[j],m2[j] = 0;
    }
}
int main(  )
{
    while( scanf( "%ld%ld",&n,&m ) ,n |m )
    {
        gf(  );
        if( m == 0 || n == 0 )
            puts( "0" );
        else
            printf( "%ld\n",m1[m] );
    }
    return 0;
}