CFR 128 C. Games with Rectangle ( Math )

題意：
給一個 N * M 的矩形。現在要做 K 次操作，每次需將原本的矩形嚴格變小，但必須邊長都是整數。問方案數對 1e9 + 7 取模。

資料規模：
1 ≤ N, M, K ≤ 1000

解法：
二維問題很常有的一個技巧，那就是發現兩個維度獨立。
考慮一維問題，那便是在 N - 1 條縱線中選取 2 * K 條線，左右界便會唯一確定。
分別計算後相乘即可。

時間 / 空間複雜度：
O( N^2 )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int MOD = ( int ) 1e9 + 7;

int C[ MAXN + 10 ][ MAXN + 10 ];
int N, M, K;

signed main(){
  {
    C[ 0 ][ 0 ] = 1;
    for( int i = 0; i < MAXN; ++i ){
      for( int j = 0; j <= i; ++j ){
        ( C[ i + 1 ][ j ] += C[ i ][ j ] ) %= MOD;
        ( C[ i + 1 ][ j + 1 ] += C[ i ][ j ] ) %= MOD;
      }
    }
  }
  ios::sync_with_stdio( 0 );
  cin >> N >> M >> K;
  if( 2 * K > N - 1 or 2 * K > M - 1 ){
    cout << 0 << endl;
  } else{
    cout << 1LL * C[ N - 1 ][ 2 * K ] * C[ M - 1 ][ 2 * K ] % MOD << endl;
  }
  return 0;
}