题目描述
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?
输入
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
输出
示例输入
1
2
2 1
2
3
4
示例输出
2
0
提示
分析：这是一道数学题。简单说来就是给出一堆式子，求x^P 的系数。求公比为2的首项是1的等比数列的和，得到P 的最大值为max(P) = (1 - 2^50) / (1 - 2) = 1125899906842623，而题目中给出P 的输入最大值inputMax(P)为1234567898765432。因此inputMax(P) < 2^51(这保证了下面的程序不会出现数组下标越界的问题)。另外，观察式子不难得出x^P的系数为P 的二进制形式中为1 的部分对应的ai 的乘积。例如对X^11，11写成2进制为(1011)2，那么其系数就是a0*a1*a3。程序如下：
#include<stdio.h>
#include<string.h>
#define MAXN 50
#define MOD 2012
int a[MAXN+];
int main(void)
{
int t, n, q, index, ans;
long long int exp; // 注意定义成int会WA, 因为据题意exp可达1234567898765432这么大 scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
memset(a, , sizeof(a));
for(int i = ; i <= n; i++)
scanf("%d", &a[i]); scanf("%d", &q);
while(q--)
{
scanf("%lld", &exp); // SDUT: C/C++评测程序只支持long long, 不支持int64 ans = index = ;
while(exp)
{
if(exp % != )
ans = (ans*a[index]) % MOD;
index++;
exp /= ;
} printf("%d\n", ans);
} } return ;
}