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; }