△2013山東省ACM競賽-Alice and BobAlice and Bob

Alice and Bob like playing

games very much.Today, they introduce a new game.

There is a polynomial like

this: (a0*x^(2^0)+1) * (a1 *

x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1). Then Alice ask Bob Q

questions. In the expansion of the Polynomial, Given an integer P, please tell

the coefficient of the x^P.

Can you help Bob answer

these questions?

The first line of the input

is a number T, which means the number of the test cases.

For each case, the first

line contains a number n, then n numbers a0, a1, ....

an-1 followed in the next line. In the third line is a number Q, and

then following Q numbers P.

1 <= T <=

20

1 <= n <=

50

0 <= ai <=

100

Q <=

1000

0 <= P <=

1234567898765432

For each question of each

test case, please output the answer module 2012.

The expansion of the

(2*x^(2^0) + 1) * (1*x^(2^1) + 1) is 1 + 2*x^1 + 1*x^2 +

2*x^3

題目大意：多項式相乘，寫幾項就發現規律了。

(a0x+1)(a1x^2+1)(a2x^4+1)

=a0a1a2x^7+a1a2x^6+a0a2x^5+a2x^4+a0a1x^3+a1x^2+a0x+1

   列出來後發現正好該數化為二進制（不用逆置），如果為1，則相乘

7:a0a1a2  

即1+2+4

6:a1a2    

 即2+4

5:a0a2    

 即1+4

4:a2      

  即4

3:a0a1    

即1+2

2:a1      

 即2

1:a0      

 即1

0:1

可以看出，對應為：

a3   a2   a1

  a0

8     4  

  2     1