首页 > 其他 > 详细

[2013山东省第四届ACM大学生程序设计竞赛]——Alice and Bob

时间:2014-05-06 19:05:05      阅读:468      评论:0      收藏:0      [点我收藏+]

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
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

来源

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

题目:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2608


这道题,当时给高恒做的,恩。

后来发现,题目跟二进制有关,(这个发现证明 知识可以当饭吃啊! )

题意就是求x的相应次方的系数。

具体做法,我看我们另一个队的小锐锐说的很详细,很赞。(<小锐锐的CSDN>)


Idea:通过观察公式可以发现: (a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1)

x的系数只是 2^0 , 2^1 ,2^2....2^n

所以可以联想到二进制(小锐锐说的= =。)

然后再看,展开式中没有指数相同的两项,所以不能合并公因式。

再加上数据量,相当庞大,感觉就是个找规律的题目。

先由题目中输入 n个数 ,假设: n=4   4个数分别为: a0=2 a1=4 a2=1 a3=3

如果求 x的10次方的系数:

10 转化为 二进制: 1010

10 1 0

a3a2 a1 a0

将二进制为1 的,相应a乘起来:  sum= a3*a1=12

同理 13:

11 0 1

a3a2 a1 a0

sum= a3*a2*a0=6

最后再注意两点:

①若发现二进制的位数大于a的个数,就输出0

②sum不要最后对2012取模,要算一次取一次模


/**************************************
***************************************
*        Author:Tree                  *
*From :http://blog.csdn.net/lttree    *
* Title : Alice and Bob               *
*Source: 第四届山东省ACM比赛         *
* Hint  : 二进制                      *
***************************************
**************************************/
#include <iostream>
using namespace std;
int arr[51];
int main()
{
    int t,n,m,i;
    long long int q,sum;
    cin>>t;
    while ( t-- )
    {
        cin>>n;
        for(i=0;i<n;++i)
            cin>>arr[i];
        cin>>m;
        while( m-- )
        {
            cin>>q;
            i=0;
            sum=1;
            // 一边求二进制,一边计算答案
            while( q!=0 )
            {
                // 如果二进制位数小于n 系数为0
                if( i>=n )   {sum=0;break;}
                if( q%2 )   sum*=arr[i];
                ++i;
                q/=2;
                sum=sum%2012;
            }
            cout<<sum<<endl;
        }
    }
    return 0;
}



[2013山东省第四届ACM大学生程序设计竞赛]——Alice and Bob,布布扣,bubuko.com

[2013山东省第四届ACM大学生程序设计竞赛]——Alice and Bob

原文:http://blog.csdn.net/lttree/article/details/25063269

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!