D - AtCoder社の冬
Editorial
/
AtCoder社の社員室は R \times C(R 行 C 列)の区画に区切られており、各区画には、社員のデスク、サーバーラックのどちらかがあるか、何もない空きスペースのどれかです。
AtCoder社のある地域の冬は寒く、暖房代をできるだけ節約するため、社員室の必要なスペースのみを区切って使用することに決めました。
しかし、資材の問題で、区画に平行な長方形の領域で区切らなければいけません。
そこで、
すると壁で囲まれた領域は X \times Y(X 行 Y 列)の区画になりました。
また、AtCoder社の社員室には、D 個のデスクと、L 個のサーバーラックがあります。
もともと、社員室に、どのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007 = 10^9+7 で割った余りを求めるプログラムを書いてください。
入力は以下の形式で標準入力から与えられる。
社員室にどのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007 = 10^9+7 で割った余りを 1 行で出力せよ。
また、出力の末尾には改行を入れること。
D+L = X \times Y の場合のテストケースに全て正解した場合、101 点満点中の 100 点が与えられる。
満点解法は非常に難しいので、部分点を確実に取ることから考えましょう。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
AtCoder社のある地域の冬は寒く、暖房代をできるだけ節約するため、社員室の必要なスペースのみを区切って使用することに決めました。
しかし、資材の問題で、区画に平行な長方形の領域で区切らなければいけません。
そこで、
- デスク、または、サーバーラックのある最も上の行のすぐ上、
- デスク、または、サーバーラックのある最も下の行のすぐ下、
- デスク、または、サーバーラックのある最も左の列のすぐ左、
- デスク、または、サーバーラックのある最も右の列のすぐ右
すると壁で囲まれた領域は X \times Y(X 行 Y 列)の区画になりました。
また、AtCoder社の社員室には、D 個のデスクと、L 個のサーバーラックがあります。
もともと、社員室に、どのようにデスクとサーバーラックの配置されていたのか、考えうるパターン数を 1000000007 = 10^9+7 で割った余りを求めるプログラムを書いてください。
入力
R C X Y D L
- 1 行目には、AtCoder社の社員室の区画の行数、列数を表す整数 R,\ C\ (1 ≦ R, C ≦ 30) がスペース区切りで与えられる。
- 2 行目には、社員室の壁に囲まれた部分の区画の行数、列数を表す整数 X,\ Y\ (1 ≦ X ≦ R,\ 1 ≦ Y ≦ C) がスペース区切りで与えられる。
- 3 行目には、社員室にある社員のデスクの数、サーバーラックの数を表す整数 D,\ L\ (D, L ≧ 0,\ 1 ≦ D+L ≦ X \times Y) がスペース区切りで与えられる。
出力
また、出力の末尾には改行を入れること。
部分点
満点解法は非常に難しいので、部分点を確実に取ることから考えましょう。
入力例 1
3 2 2 2 2 2
出力例 1
12
- このケースは D+L=X \times Y を満たすため、部分点のテストケースに含まれる可能性があります。
- 以下の 12 通りの配置が考えられます。ここで
D
はデスク、L
はサーバーラック、.
は何もないことを表します。
DD DL DL LD LD LL .. .. .. .. .. .. LL DL LD DL LD DD DD DL DL LD LD LL .. .. .. .. .. .. LL DL LD DL LD DD
入力例 2
4 5 3 1 3 0
出力例 2
10
- このケースは D+L=X \times Y を満たすため、部分点のテストケースに含まれる可能性があります。
入力例 3
23 18 15 13 100 95
出力例 3
364527243
- このケースは D+L=X \times Y を満たすため、部分点のテストケースに含まれる可能性があります。
- 社員室の配置パターンは 145180660592914517790287604376765671109248284280228061640640 通りで、これを 10^9+7 で割った余りである 364527243 を出力してください。
入力例 4
30 30 24 22 145 132
出力例 4
976668549
- このケースは D+L=X \times Y を満たさないため、部分点のテストケースに含まれることはありません。
- 無理に正解しようとせず、余裕のある人だけ挑戦してみてください。