Chef has a Spaghetti Garden
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is tending a really large spaghetti garden. This garden consists of many spaghetti trees. Specifically, there is a spaghetti tree planted for each lattice point location (x, y) with x, y ≥ 0. (Yes, there are an infinite number of trees in Chef's garden!)
It's the 1st of April, so it's harvest time for Chef. Chef plans to harvest all spaghetti strands within a certain region today. In case you didn't know, a spaghetti tree bears spaghetti strands as its fruits.
Specifically, Chef plans to harvest all spaghetti strands hanging from every spaghetti tree whose location (x, y) is within the interior or boundary of a certain polygon with N vertices. Also, the spaghetti tree located at (x, y) currently bears exactly Fx+y fruits, where Fk satisfies the following fourth-order recurrence:
Fk = a·Fk-1 + b·Fk-2 + c·Fk-3 + d·Fk-4
How many strands of spaghetti will Chef be able to harvest today? Since this number can be very large, output it modulo 109 + 9. (Note: this is slightly different from the usual mod.)
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains nine space separated integers N, a, b, c, d, F0, F1, F2, and F3.
After that, N lines follow. The ith line contains two integers xi and yi, denoting that (xi, yi) is the ith vertex of the polygon in counterclockwise order.
For each test case, output a single line containing the integer: the answer for that test case.
- 0 ≤ a, b, c, d, F0, F1, F2 F3 < 109 + 9
- The polygon is simple and non-degenerate.
- 1 ≤ T ≤ 2000
- 3 ≤ N ≤ 16
- The sum of the N in a single test file is ≤ 6000
SubtasksSubtask #1 (10 points):
- 0 ≤ xi, yi ≤ 100
- 0 ≤ xi, yi ≤ 104
- 0 ≤ xi, yi ≤ 109
Input: 2 4 1 2 3 4 0 1 2 3 1 1 2 1 2 2 1 2 4 1 2 3 4 0 1 2 3 1 1 3 1 3 3 1 3 Output: 18 153
In both test cases, we have Fk = k for 0 ≤ k ≤ 3 and Fk = Fk-1 + 2·Fk-2 + 3·Fk-3 + 4·Fk-4. So you can check that F4 = 10, F5 = 26 and F6 = 63
- In the first test case, Chef will harvest all spaghetti strands in the locations (1, 1), (1, 2), (2, 1), (2, 2). The total number is F1+1 + F1+2 + F2+1 + F2+2 = F2 + F3 + F3 + F4 = 18
- In the second test case, Chef will harvest all spaghetti strands in the locations (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3). The total number is F1+1 + F1+2 + F1+3 + F2+1 + F2+2 + F2+3 + F3+1 + F3+2 + F3+3 = F2 + F3 + F4 + F3 + F4 + F5 + F4 + F5 + F6 = 153
|Time Limit:||9 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.