Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Sure. We can think of them as independent due to the following argument. Let's say we have two sequences, one for each dimension, e.g.
- [0, n], [1, n - 1], ...
- [0, m], [2, m - 1], ...
- which represent the left/right bounds and top/bottom bounds of the box at each of the k steps, respectively. So the first box is obviously (0, 0) to (n, m) and the second is (1, 2) to (n - 1, m - 1). We observe that for any two sequences of the left/right bounds and top/bottom bounds we get exactly one sequence of boxes. It suffices then to count the number of such sequences and multiply them together.
- To count the sequences, we look at just one of the sequences above, e.g. [0, n], [1, n - 1], [3, n - 2], ... and rewrite it "in order" like this: 0, 1, 3, ..., n - 2, n - 1, n. We know that 0 is always at the start and n is always at the end and there are exactly 2k values from 1 to n - 1 (two for each of the k intervals). Moreover, for any 2k values in [1, n - 1] we can uniquely construct the k intervals by taking the outermost values to be the first interval, then the next outermost to be the second, etc. For example: 0, 3, 4, ..., n - 3, n - 2, n becomes [0, n], [3, n - 2], [4, n - 3], ....
- Thus we have a one-to-one correspondence between such sequences and sets of 2k values in the interval [1, n - 1] of which there are C(n - 1, 2k).
- */
- ll NCR[3000][3000];
- ll ncr(int n,int r)
- {
- if(r>n)return 0;
- if(n==r)return 1;
- if(r==1)return n;
- if(NCR[n][r])return NCR [n][r];
- return NCR[n][r] = (ncr(n-1,r)%mod+ncr(n-1,r-1)%mod)%mod;
- }
- int main()
- {
- booster()
- ///read("input.txt");
- int n,m,k;
- cin>>n>>m>>k;
- cout<<(ncr(n-1,2*k)*ncr(m-1,2*k))%mod;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement