Alice and Bob
Time Limit: 1000ms Memory limit: 65536K
题目描述
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.
示例输入
1
2
2 1
2
3
4
示例输出
2
0
提示
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转换成一个二进制的数，然后分别乘上系数。
一开始挺难理解的，T给我讲了，才明白了，其实可以在纸上自己先算算再自己写出二进制来，推一下，就可以理解了
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
int main()
{
int n ;
cin>>n ;
while(n--)
{
int t ;
int a[],b[] ;
cin>>t ;
memset(a,,sizeof(a));
for(int i = ; i <= t- ; i++)
{
cin>>a[i];
}
int p;
cin>>p;
for(int i = ; i <= p ; i++)
{
long long q ;
cin>>q ;
int x = ;
if(q == )
{
cout<<""<<endl;
continue ;
}
while(q)
{
b[x++] = q% ;
q = q/ ;
}
int sum = ;
for(int j = ; j <= x- ; j++)
{
if(b[j])
{
sum = sum*a[j]%;
}
}
cout<<sum<<endl ;
}
}
return ;
}