Light OJ 1326 - Race

Problem No: 1326-Race

Both combinatorics and dynamic problem concept is used in this problem. We calculate how many ways the race can finish.

1. #include<bits/stdc++.h>
3. using namespace std;
5. #define ll long long
6. #define N 1000
7. #define mod 10056
9. ll ncr[N + 1][N + 1];
10. ll dp[N + 1];
12. int main()
13. {
14.     ll xx, yy;
15.     int i, j;
16.     ncr[0][0] = 1;
17.     for (i = 1; i <= N; i++) {
18.         for (j = 0; j <= N; j++) {
19.             if (j > i) ncr[i][j] = 0;
20.             else if (j == i || j == 0) ncr[i][j] = 1;
21.             else ncr[i][j] = (ncr[i - 1][j - 1] + ncr[i - 1][j]) % mod;
22.         }
23.     }
24.     dp[0] = 1;
25.     for (int i = 1; i <= N; i++) {
26.         xx = 0;
27.         for (int j = 1; j <= i; j++) {
28.             yy = (ncr[i][j] * dp[i - j]) % mod;
29.             xx = (xx + yy) % mod;
30.         }
31.         dp[i] = xx;
32.     }
33.     int n, t, id = 0;
34.     scanf ("%d", &t);
35.     while (t--) {
36.         scanf ("%d", &n);
37.         ll ans = dp[n];
38.         printf ("Case %d: %lld\n", ++id, ans);
39.     }
40.     return 0;
41. }