状态转移方程为：num[n][k]=num[n-1][k-1]+num[n-k][k]

表示n个Apple分给k个People，

1).若k个人不能获得一样的，则为了满足题意，需要将最后一个人先分1个，再将剩余n-1的分给k-1个人;

2).若能，则就变成了将n-k个Apple分给k个People的子过程。

/*  * soj3291.c  *  *  Created on: 2011-10-10  *      Author: bjfuwangzhu */ #include
     
       #define nmod 10009 #define nmax 1010 int num[nmax][nmax]; void init() {
   int i, j; for (i = 0; i < nmax; i++) {
           num[i][0] = 0, num[0][i] = 0;     } for (i = 1; i < nmax; i++) {
   for (j = 1; j < nmax; j++) {
   if (i < j) {
                   num[i][j] = 0;             } else if (i == j) {
                   num[i][j] = 1;             } else {
                   num[i][j] = (num[i - 1][j - 1] + num[i - j][j]) % nmod;             }         }     } } int main() {
   #ifndef ONLINE_JUDGE     freopen("data.in", "r", stdin); #endif int t, n, k;     init();     scanf("%d", &t); while (t--) {
           scanf("%d %d", &n, &k);         printf("%d\n", num[n][k]);     } return 0; }