TopCoder SRM 597 - 900: LittleElephantAndBoard

Problem Statement

给一个2 * M的表格，
现在你要将其中的R个格子涂成红色，G个格子涂成绿色，B个格子涂成蓝色，
并且要满足：任意两个相邻格子的颜色不同；每种颜色在任意一个2* 2矩阵中都至少出现一次。
求方案数10^9+7取模。

数据范围：
2 <= M <= 10^6
保证R+G+B = 2 * M

Little Elephant from the Zoo of Lviv has a board with 2 rows and M columns. Each cell of the board must be painted in one of three colors: red, green, or blue.

The board is called magical if and only if it has the following properties:

No two adjacent cells share the same color. (Two cells are adjacent if they share an edge.)
Every 2x2 block contains at least one cell of each of the three colors.

You are given four ints M, R, G and B. Let X be the total number of different magical boards with 2 rows and M columns that contain exactly R red cells, G green cells, and B blue cells. Return the value (X modulo 1,000,000,007).

Definition

Class LittleElephantAndBoard
Method getNumber
Parameters int , int , int , int
Returns int
Method signature int getNumber(int M, int R, int G, int B)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Constraints

M will be between 2 and 1,000,000, inclusive.
R, G and B will each be between 0 and 1,000,000, inclusive.
R+G+B will be equal to 2M.

Test cases

input
- M 2
- R 2
- G 1
- B 1
output
Returns 4

note

The following 4 different magical boards are possible in this case:
input
- M 2
- R 2
- G 2
- B 0
output
Returns 0

note

No magical board is possible in this case.
input
- M 10
- R 7
- G 7
- B 6
output
Returns 496
input
- M 474
- R 250
- G 300
- B 398
output
Returns 969878317

back to the menu

SRM 597 1 900 LittleElephantAndBoard

Problem Statement

Definition

Limits

Constraints

Test cases