UPC2222: Alice and Bob

UPC2222: Alice and Bob

2222: Alice and Bob

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 263

Solved: 77

[

​​Submit​​][

​​Status​​][

​​Web Board​​]

Description

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?

Input

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

Output

For each question of each test case, please output the answer module 2012.

Sample Input

122 1234

Sample Output

20

HINT

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

Source

​​2013年山东省第四届ACM大学生程序设计竞赛​​

#include#include#includeusing namespace std;int main(){ int t; cin>>t; while(t--) { int n,a[60]; cin>>n; for(int i=0;i>a[i]; int q; cin>>q; while(q--) { stacks; long long p; cin>>p; int x,cnt=-1; int result=1; while(p){ cnt++; x=p%2; s.push(x); p/=2; } if(cnt > n-1){ printf("0\n"); } else{ while(!s.empty()) { if(s.top()==1) { result *= a[cnt]; if(result > 2012) result %= 2012; } s.pop(); cnt--; } printf("%d\n",result); } } } return 0;}

后来一直WA,原因就是把stack定义在了外面，会有如果cnt超了，stack里会有剩余的数值，所以每次用都要先定义

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。