All submissions for this problem are available.
Consider an infinitely large chess table.
From the cell (0, 0), our knight has to move to the cell (X, Y) by the rule:
our knight could only move from a cell (u, v) to the cell (u+AX, v+AY) or (u+BX, v+BY) in one move.
Note that it may be different from ordinary knight's move of chess.
In addition, there is K blocked cell(s) on the table where the knight could not move on.
Your task is to count how many distinct ways the knight could complete his mission.
Two ways are called "distinct" if and only if they have different numbers of steps or there exists i such that they are in different cells after i-th step.
Note that our knight may continue to move after he reaches the cell (X, Y).
The first line contains an integer T, denoting the number of test cases. Each test case is described as follows:
- The first line contains 3 integer X, Y, K.
- The second line contains 4 integers AX, AY, BX, BY.
- The third line contains K pair(s) of integers, each represents co-ordinate of a blocked cell. This line does not exist if K = 0.
For each test case, output on a line the number of ways found modulo 1000000007 (109+7).
If there are infinitely many ways, then output -1 instead.
1 ≤ T ≤ 5
0 ≤ K ≤ 15
The absolute values of all other input values are at most 500.
(0, 0) is not a blocked cell.
(X, Y) is not a blocked cell.
Input: 3 3 3 0 1 2 2 1 9 9 2 1 2 2 1 1 2 6 6 1 1 0 0 0 0 0 Output: 2 4 0
In the first and second examples, our knight's move is the similar to ordinary knight's, but only 2 directions are allowed. In the first example, there are 2 ways (0, 0) -> (1, 2) -> (3, 3) and (0, 0) -> (2, 1) -> (3, 3).
In the third example, our knight's cannot move toward, so our knight's cannot complete his mission.
|Tags||anhdq, dynamic-programming, gauss-elim, number-theory, sep12|
|Time Limit:||0.9 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.