本文主要是介绍[2013山东ACM省赛] Alice and Bob，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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?
输入
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
输出
示例输入
122 1234
示例输出
20
提示
来源
解题思路：
求多项式相乘展开式中x的某一指数的系数。
(a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1)给定这个式子，观察x的指数，2^0 2^1 2^2 。。很容易联想到二进制。
后来发现有规律，展开式中没有指数相同的两项，也就是说不能合并公因式。而某一x指数的系数化为二进制以后就可以找到规律了。
比如 求指数为13的系数，把13化为二进制 1 1 0 1 从右到左分别对应 a0 a1 a 2 a3 ，那么所求系数就是 a0 * a2 * a 3
再举例说明：
代码：
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
int a[51];
int t,n,q;
long long p;
int main()
{
cin>>t;while(t--)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>q;
while(q--)
{
stack<int>s;
cin>>p;
int result=1;
int cnt=-1; //这里使用了-1，为了方便，因为a数组是从0开始的
int yu;
while(p) //把数化为二进制存到栈中
{
cnt++;
yu=p%2;
s.push(yu);
p/=2;
}
if(cnt>n-1) //当数的二进制位数大于n时，不存在直接输出0
{
cout<<0<<endl;
continue;
}
else
{
while(!s.empty())
{
if(s.top()==1)
{
result*=a[cnt];//取数相乘
if(result>2012)
result%=2012;
}
s.pop();
cnt--;
}
}
cout<<result<<endl;
}
}
return 0;
}
这篇关于[2013山东ACM省赛] Alice and Bob的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
