山东省第四届ACM省赛题——Alice and Bob（二进制）-白红宇

山东省第四届ACM省赛题——Alice and Bob（二进制）

阅读量：2343 次

发布时间：2019-05-10

本文共 1520 字，大约阅读时间需要 5 分钟。

题目描述

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.

示例输入

2 1

示例输出

提示

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

明显不可能让我们一个个算各项的系数

对p取二进制，样例中的3，二进制是11，对应了a2=1,a1=2都要相乘，所以结果是1*2=2。

2的二进制是10，对应了只有a2=1,a1对应的位置是0不能相乘，所以结果是2.

4的二进制位数超过了系数的个数，直接输出0。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        //#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #define MAXN 100010#define mod 2012#define INF 0x3f3f3f3fusing namespace std;int a[55];int main(){ ios::sync_with_stdio(false); long long t,n,q,p,sum; cin>>t; while(t--) { cin>>n; for(int i=0;i
              
               >a[i]; cin>>q; while(q--) { cin>>p; int i=0; sum=1; while(p!=0) { if(i>=n) { sum=0; break; } if(p%2==1) sum*=a[i]; i++; p/=2; sum=sum%mod; } cout<
               
                <