NOIP '18 P5 - Grid-filling Game

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

There is an n \times m grid. A valid path P from the upper left corner to the bottom right corner is a path such that movements are only allowed in the right or in the down directions, and we may use a string w(P) to represent the path in the way that if in the i-th step we move right then the i-th character of w(P) is R while if in the i-th step we move down then the i-th character of w(P) is D. The length of w(P) shall be n+m-2.

Now we are going to fill the grids with number 0 or 1. For a valid path P, if we write down the numbers in the grids on the path (including the start and the end, in the order we visit the grids), we get a string of length n+m-1, s(P). Compute the number of ways to fill the grids with 0 or 1, modulo 10^9 + 7, such that for any two valid paths P_1, P_2, if w(P_1) > w(P_2) in the lexicographic order, then s(P_1) \le s(P_2) in the lexicographic order.

Input Specification

The input consists of one line with two integers n,m separated by a space denoting the size of the grid. n denotes the number of rows in the grid, while m denotes the number of columns in the grid.

Output Specification

The output consists of one line containing an integer denoting the number of valid ways to fill the grid with 0 and 1 subject to the constraint mentioned in the statement, modulo 10^9 + 7.

Sample Input 1

2 2

Sample Output 1



The two possible paths from the upper-left corner to the bottom-right corner have w(P_1) = \texttt{RD} and w(P_2) = \texttt{DR}. As a result, the invalid ways to fill the grid with 0 and 1 are exactly the ways to fill the grids such that s(P_1) > s(P_2), which happens if and only if when the upper-right corner is 1 and the bottom-left corner is 0. Therefore, the answer in this case shall be 2^4 - 2^2 = 12.

Sample Input 2

3 3

Sample Output 2


Sample Input 3

5 5

Sample Output 3



Test Case n \le m \le
1-4 3 3
5-10 2 10^6
11-13 3 10^6
14-16 8 8
17-20 8 10^6


There are no comments at the moment.