All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Henry and Derek are waiting in a room. They have successfully qualified for the Snackdown Finals 2016, and decide to pass the time by playing a new game.
Before the game starts, they select N numbers: v(0), v(1), ..., v(N-1). These numbers will stay fixed throughout the game.
The initial state of the game consists of K integers x1, x2, ..., xK, each of which is in the range [0, N-1]. Thus, there are NK distinct states all in all. Then the players take turns, starting with Henry. In a turn, a player selects one of the integers, say xi, and decreases it by some positive multiple of 2v(xi). However, this is only valid if the resulting number is nonnegative. A player loses if there are no more valid moves left.
Henry and Derek have gotten really good at playing this game, so much that they have figured out the optimal strategy, and they always play optimally! This made the game really boring for them, because the winner is solely determined by the initial state of the game. So instead of playing the game, they decided to just answer the following question instead:
Of all the NK possible initial states, how many of them result in a win for Henry?
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 two integers, N and K.
The second line contains N space-separated integers v(0), v(1), ..., v(N-1).
For each test case, output a single line containing a single integer, the number of initial states that result in a win for Henry. This number can be very large, so output it modulo 109 + 7.
- 1 ≤ T ≤ 3
- 1 ≤ K ≤ 106
- 1 ≤ N ≤ 105
- 0 ≤ v(i) ≤ 104
Input: 3 2 3 1 0 5 3 2 0 1 0 0 5 3 2 0 1 0 1 Output: 4 94 100
In the first case, the following initial states result in a win for Henry: [1,1,1], [0,0,1], [0,1,0], [1,0,0].
|Time Limit:||6 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.