首页 > 代码库 > [2013山东ACM省赛] Alice and Bob

[2013山东ACM省赛] Alice and Bob

2024-07-03 03:41:19   227人阅读

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.

示例输入

122 1234

示例输出

20

提示

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

来源

 2013年山东省第四届ACM大学生程序设计竞赛

 

解题思路：

求多项式相乘展开式中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;  }


 


联系
我们