山东省第四届省赛Problem F:Alice and Bob（找规律）

B - Problem F:Alice and Bob Time Limit:1000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu Submit  Status  use MathJax to parse formulas

Description

Alice and Bob like playing games very much.Today, they introduce a new game.

There is a polynomial like this: (a₀*x^(2^0)+1) * (a₁ * x^(2^1)+1)*.......*(a_n-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 a₀, a₁, .... a_n-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 <= a_i <= 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

题目意思就是给你n个数，q个查询，求2的q次放的系数是多少

假如n = 4.n个数分别a0,a1,a2,a3

把多项式拆开后：

让我们来列一个表格

P12345672^02^12^1+2^02^22^2+2^02^2+2^12^2+2^1+2^0a0a1a0*a1a2a2*a0a1*a2a2*a1*a0

答案很明显了，查询P的ans *= a[P的二进制数]

且当p的最高位二进制数大于n时，ans = 0;

代码如下

#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> using namespace std; #define maxn 110 #define INF 0x3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #define For(i,n) for(i=0;i<n;i++) #define mod 2012 typedef long long ll; int gcd(int a,int b){return b?gcd(b,a%b):a;} int main() { ll n,a[maxn],t,q,p; ll i,j; ll num; ll ans; cin >>t; while(t--){ cin >> n; int leng; mem(a,0); For(i,n) cin >> a[i]; cin >>q; ll k; while(q--){ ans = 1; i = 0; num = 0; cin >> p; num = 1; while(p){ if(p&1 && i<n) ans = ans * a[i]%mod; else if(i >= n){ ans = 0; break; } p>>=1; i++; } cout << ans%mod << endl; } } return 0; }