Bored of Nim
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Rahul and Rashi are bored of playing the game of Nim all day. More so, Rahul has been losing all the games. Actually, the array of stone piles for a game is always selected by Rashi from a huge N-length array A. This selected array is always a subarray of A.
Rahul, now frustrated by his losing streak, insists that he would play the next game only if she chooses a game array of length m.
Can you find the number of such subarrays that Rashi can choose so that Rahul still loses? Moreover, since the value of m is decided by Rahul, can you do this for all possible values of m?
Please note that Rahul is always the first player.
The first line contains an integer T, the number of test cases to follow. In each of the test cases, the first line contains a single integer N, and the next line contains N integers, representing the array A.
Output the results of each test case on a new line. For each test case, output the results for all values of m, that is, m = 1, m = 2 ... m = N, separated by a single space.
- 1 ≤ T ≤ 3
- 1 ≤ N ≤ 105
- 0 ≤ A[i] ≤ 109
- 1 ≤ m ≤ N
2 6 1 2 3 2 1 3 4 1 1 1 1
0 0 3 0 0 1 0 3 0 1
For the first test case and m = 3, required sub-arrays are [1,2,3], [3,2,1] and [2,1,3].
|Tags||code_master01, cook59, fft, game-theory, medium-hard|
|Time Limit:||5 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.