Lightoj 1326 - Race

http://lightoj.com/volume_showproblem.php?problem=1326

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long int
4. #define M 10056
5. int DP[1005][1005];
6. int dp[1005];
7. int bc(int n, int k){
8.     int i, j;
9.     for (i = 0; i <= n; i++){
10.         for (j = 0; j <=  k; j++){
11.             if (j == 0 || j == i)
12.                 DP[i][j] = 1;
13.  
14.             else
15.                 DP[i][j] = (DP[i-1][j-1]%M + DP[i-1][j]%M)%M;
16.         }
17.     }
18. }
19. int main(){
20.     bc(1000, 1000);
21.     dp[0] = dp[1] = 1;
22.     dp[2] = 3;
23.     for(int i = 3; i <= 1000; i++){
24.         for(int j = i-1; j>=0; j--){
25.             dp[i]+= (dp[j]%M)*(DP[i][i-j]%M)%M;
26.             dp[i]%=M;
27.         }
28.     }
29.     /*
30.     for(int  i = 0; i <=1000; i++){
31.         for(int j = 0; j <=1000; j++){
32.             cout<<DP[i][j]<<" ";
33.         }
34.         cout<<endl;
35.     }
36.     */
37.     //int n;
38.     //scanf("%d", &n);
39.     //for(int i = 1; i<10; i++) cout<<dp[i]<<" ";
40.     int ts;
41.     scanf("%d", &ts);
42.     for(int i = 1; i <= ts; i++){
43.         int n;
44.         scanf("%d",&n);
45.         printf("Case %d: %d\n", i, dp[n]);
46.     }  
47.     return 0;
48. }