位运算 2013年山东省赛 F Alice and Bob

 1 /*
 2     题意： 求(a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1) 式子中，x的p次方的系数
 3     二进制位运算：p = 2 ^ i + 2 ^ j + 2 ^ k  + ...，在二进制表示下就是1的出现
 4            例如：10 的二进制 为1010，10 = 2^3 + 2^1 = 8 + 2，而且每一个二进制数都有相关的a[i]，对p移位运算，累计取模就行了
 5 */
 6 #include <cstdio>
 7 #include <cmath>
 8 #include <algorithm>
 9 #include <iostream>
10 #include <cstring>
11 using namespace std;
12 
13 const int MAXN = 1e6 + 10;
14 const int INF = 0x3f3f3f3f;
15 
16 int main(void)        //F Alice and Bob
17 {
18     //freopen ("F.txt", "r", stdin);
19     
20     int t;
21     while (scanf ("%d", &t) == 1)
22     {
23         while (t--)
24         {
25             int n, a[100], q;
26             long long p;
27             scanf ("%d", &n);
28             for (int i=0; i<n; ++i)
29             {
30                 scanf ("%d", &a[i]);
31             }
32             scanf ("%d", &q);
33             
34             while (q--)
35             {
36                 scanf ("%lld", &p);
37                 int tmp = 1;    int i = 0;
38                 while (p)
39                 {
40                     if (i >= n)
41                     {
42                         tmp = 0;    break;
43                     }
44                     if (p & 1)        tmp *= a[i];
45                     ++i;
46                     p >>= 1;
47                     tmp %= 2012;
48                 }
49                 printf ("%d
", tmp);
50             }            
51         }
52     }
53     
54     return 0;
55 }