uva 10943 数学

很容易想到插板法的模型，即：n个没有区别的小球放到m个不同的盒子里（允许某些盒子为空）的方法数c[n + m - 1][m - 1]。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int MOD = 1000000;
 7 const int N = 500;
 8 int c[N][N];
 9 
10 void init()
11 {
12     c[0][0] = 1;
13     for ( int i = 1; i < N; i++ )
14     {
15         c[i][0] = c[i][i] = 1;
16         for ( int j = 1; j < i; j++ )
17         {
18             c[i][j] = ( c[i - 1][j] + c[i - 1][j - 1] ) % MOD;
19         }
20     }
21 }
22 
23 int main ()
24 {
25     init();
26     int n, m;
27     while ( scanf("%d%d", &n, &m) != EOF )
28     {
29         if ( n == 0 && m == 0 ) break;
30         printf("%d
", c[n + m - 1][m - 1]);
31     }
32     return 0;
33 }