Light OJ - 1095

Problem No: 1095 - Arrange the Numbers

This problem has two parts. This is a typical combinatorics problem.

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