No.584 赤、緑、青の色塗り
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 :
nmnmnmnmnmnmnm
/ テスター :
tubo28
タグ : / 解いたユーザー数 42
作問者 :
nmnmnmnmnmnmnm
/ テスター :
tubo28
問題文最終更新日: 2017-10-28 00:21:31
問題文
$1$行$N$列のまだ色が塗られていないマスがある。
以下のルールで色塗りを行う。
・赤、緑、青の色でそれぞれ指定された数だけマスを塗る。
・空白のマスが残っても良い。空白のマスは色が塗ってあるマスとはみなさない。
・同じ色は各列隣り合った両方のマスに塗ることはできない。
・異なる色であれば連続して$2$つのマスまで隣り合って色を塗っても良い。
・連続して$3$つ以上のマスに色を塗ることはできない。
以上のルールで色を塗る方法は何通りか？
$1000000007$で割った余りを答えよ。
入力
$N$ $R$ $G$ $B$
$N$、$R$、$G$、$B$は整数。$1\le N \le 3000$。$0\le R,G,B \le 3000$。
$N$はマスの列数。$R$、$G$、$B$はそれぞれ赤、緑、青で塗るべきマスの数。
出力
答えを1行で出力せよ。
答えとなる塗り方が存在しない場合は0通りを答えとする。
最後に改行を忘れずに。
サンプル
サンプル1
入力
5 2 0 2
出力
4
左から
「赤、青、空白、赤、青」
「赤、青、空白、青、赤」
「青、赤、空白、赤、青」
「青、赤、空白、青、赤」
以上の4通りで色を塗ることができます。
サンプル2
入力
3 2 0 0
出力
1
左から「赤、空白、赤」の1通りしかありません。
サンプル3
入力
7 0 1 0
出力
7
7つのマスのいずれか1つを緑で塗ります。答えは7通りです。
サンプル4
入力
3 1 1 1
出力
0
赤、緑、青で$1$つずつ色を塗らなければなりません。
しかし、連続して$3$つ以上のマスに色を塗ることはできません。
塗る方法がないので答えは$0$通りです。
サンプル5
入力
6 2 1 1
出力
54
サンプル6
入力
300 10 20 0
出力
470935914
答えは1000000007で割った余りになるので注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。