Coloring in Hypercube
All submissions for this problem are available.
In an N-dimensional grid the co-ordinates of a cell are denoted as X1, X2, ..., XN. Any cell with negative co-ordinate are colored white. The origin cell (the one with all zero co-ordinates) is colored as black. The color of a cell in (X1, X2, ..., XN) depends on the N cells with co-ordinates (X1-1, X2, ..., XN), (X1, X2-1, ..., XN), ...., (X1, X2, ..., XN-1). The cell is colored white if and only if the number of black colored cells among these N co-ordinates are even, otherwise the cell is colored black.
You are given the starting and ending co-ordinate of sub-hypercube. You need to compute how many hyper cells in this sub hypercube are colored black.
First line of the input contains T the number of test cases. Each test case starts with a line containing N the dimension of the hypercube. The second line contains N integers denoting the co-ordinate of the starting cell of the hypercube. The third line contains N integers denoting the co-ordinate of the ending cell of the hypercube.
For each test case, output the number of black colored cells in the given hypercube. Since the result can be too big so output the result modulo 1000000009.
3 3 4 0 4 7 9 8 2 0 3 10 9 4 0 3 0 2 6 8 1 5
9 32 22
T < 51 0 < N < 9
All the co-ordinates will be non negative integers with at most 15 digits.
|Tags||aug11, hard, satej|
|Time Limit:||0.66 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.