No.584 Red, Green, and Blue Coloring
タグ : / 解いたユーザー数 42
作問者 :
nmnmnmnmnmnmnm
/ テスター :
tubo28
Problem Statement
There is a grid of $1$ row and $N$ columns whose cells have not been colored yet.
Color the cells according to the following rules.
・Color exactly the specified number of cells with each of the colors red, green, and blue.
・Blank cells may remain. A blank cell is not regarded as a colored cell.
・The same color cannot be used on both cells of a pair of adjacent columns.
・If the colors are different, up to $2$ consecutive cells may be colored next to each other.
・It is not allowed to color $3$ or more consecutive cells.
How many ways are there to color the cells under the rules above?
Output the answer modulo $1000000007$.
Input
$N$ $R$ $G$ $B$
$N$, $R$, $G$, $B$ are integers. $1\le N \le 3000$. $0\le R,G,B \le 3000$.
$N$ is the number of columns of cells. $R$, $G$, $B$ are the numbers of cells to be colored red, green, and blue, respectively.
Output
Output the answer in one line.
If there is no valid way of coloring, the answer is 0 ways.
Do not forget the newline at the end.
Sample
Sample 1
Input
5 2 0 2
Output
4
From the left,
"red, blue, blank, red, blue"
"red, blue, blank, blue, red"
"blue, red, blank, red, blue"
"blue, red, blank, blue, red"
These are the 4 ways to color the cells.
Sample 2
Input
3 2 0 0
Output
1
There is only 1 way: from the left, "red, blank, red".
Sample 3
Input
7 0 1 0
Output
7
Color any 1 of the 7 cells green. The answer is 7 ways.
Sample 4
Input
3 1 1 1
Output
0
You must color $1$ cell each with red, green, and blue.
However, it is not allowed to color $3$ or more consecutive cells.
Since there is no way to color the cells, the answer is $0$ ways.
Sample 5
Input
6 2 1 1
Output
54
Sample 6
Input
300 10 20 0
Output
470935914
Note that the answer is taken modulo 1000000007.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。