SCALES - Balancing the Stone
You are given scales for weighing loads. On the left side lies a single stone of known weight W<2N. You own a set of N different weights, weighing 1, 2, 4, ..., 2N-1 units of mass respectively. Determine how many possible ways there are of placing some weights on the sides of the scales, so as to balance them (put them in a state of equilibrium). Output this value modulo a small integer D.
The input begins with the integer t, the number of test cases. Then t test cases follow.
For each test case, the first line contains three integers: N L D, where N denotes the number of weights at your disposal, L is the length of the binary representation of number W, and D is the modulus (1<= L<= N<= 1000000, 2<= D<=100). The second line contains the value of W, encoded in the binary system as a sequence of exactly L characters 0 or 1 without separating spaces.
For each test case, output a single line containing one integer - the calculated number of possible weight placements, modulo D.
Sample input: 2 6 4 6 1000 6 6 100 100110 Sample output: 3 5Warning: large Input/Output data, be careful with certain languages
For first case, on right side weight 1000 (=8) is already present.
In first sample input how output is 3, there can be 4 cases L-1 R-1, L-1+1 R-2, L-1+1+2 R-4, L-1+1+2+4 R-8,, please help
please explain test case 1
use iteratve DP watch out for mod and make sure that the array size is big enough
unexpected AC in 1 go :) good problem (y)
Ghost Of Perdition:
Totally Awesome Problem !!
Last edit: 2013-08-20 13:22:21