Advertisement
RaFiN_

cf-128c

Feb 26th, 2019
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. /*
  2. 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.
  3.  
  4. [0, n], [1, n - 1], ...
  5. [0, m], [2, m - 1], ...
  6.  
  7. 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.
  8.  
  9. 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], ....
  10.  
  11. 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).
  12.  
  13.  
  14. */
  15.  
  16. ll NCR[3000][3000];
  17.  
  18. ll ncr(int n,int r)
  19. {
  20.     if(r>n)return 0;
  21.     if(n==r)return 1;
  22.     if(r==1)return n;
  23.     if(NCR[n][r])return NCR [n][r];
  24.     return NCR[n][r] = (ncr(n-1,r)%mod+ncr(n-1,r-1)%mod)%mod;
  25. }
  26.  
  27.  
  28. int main()
  29. {
  30.     booster()
  31.     ///read("input.txt");
  32.     int n,m,k;
  33.     cin>>n>>m>>k;
  34.     cout<<(ncr(n-1,2*k)*ncr(m-1,2*k))%mod;
  35.  
  36.     return 0;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement