Codeforces 128 C. Games with Rectangle

問題

nxmの方眼紙に、各頂点が格子点であるような長方形をk個書く。
i番目の長方形はi-1番目の長方形の真に内部になければならない。

長方形の書き方は何通りあるか、mod 10^9+7で求めよ。

制約条件

n,m,k≦1000

方針

長方形の縦と横で独立に考えてよい。
縦の線の選び方が何通りあるかを考える。


方眼紙の縦の直線n-1本のうち、長方形の辺になるような直線を2*k本選ぶと、
長方形が入れ子になっているという条件から、長方形の書き方が一意に定まる。


すなわち、縦の線の選び方はn-1C2*k通りあることがわかる。


これを横についても同様に考え、それぞれの場合の数を掛け合わせてやればよい。

ソースコード

const int mod=(int)1e9+7;
ll dp[1001][1001];
ll C[1001][1001];

void run(){
  int n,m,k;
  cin>>n>>m>>k;
  rep(i,1001)rep(j,i+1)C[i][j]=(i==0||i==j?1:C[i-1][j]+C[i-1][j-1])%mod;
  if(n-1<k*2||m-1<k*2)cout<<0<<endl;
  else cout<<C[n-1][k*2]*C[m-1][k*2]%mod<<endl;
}