山东省第四届ACM大学生程序设计竞赛-Alice and Bob（二进制&&找规律）

小咪咪 2022-07-28 08:59 134阅读 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
    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

## 来源 ##

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

## 题目意思： ##

给定(a0\*x^(2^0)+1) \* (a1 \* x^(2^1)+1)\*.......\*(an-1 \* x^(2^(n-1))+1)

这个式子的系数a，展开这个式子后，求x^q的系数。

### 解题思路： ###

### (a0\*x^(2^0)+1) \* (a1 \* x^(2^1)+1)\*.......\*(an-1 \* x^(2^(n-1))+1) ###

展开看看：

当n=0：

1+a0\*x^20

当n=1：

1+ a0 \*a1\*x^20\*x^21\+a1\*x^21\+a0\*x^20

当n=2：

1+ a0 \*a1\*a2\*x^20\*x^21\*x^22\+a2\*x^22\+a1\*x^21\+a0\*x^20\+a2\*a1\*x^22\*x^21\+a1\*a0\*x^21 \*x^20\+ a2\*a0\*x^22\*x^20

………………

所以展开式中不存在可以合并同类项的情况，直接借助系数a就可以运算。

先看下面这张表（q在题目中是x的指数）：

q 二进制 x的指数

1 1 (20)

2 10 (21)

3 11 (21 \+20)

4 100 (22)

5 101 (22 \+20)

6 110 (22 \+21)

7 111 (22 \+21\+20)

8 1000 (23)

9 1001 (23\+20)

发现了什么规律？

对了，就是把指数转换成二进制数，再把二进制数中所有“1”的权值都加起来！！

举个栗子：

q=3时，x^3的系数=a\[1\]\*a\[0\]；

q=6时，x^6的系数=a\[2\]\*a\[1\]；

q=7时，x^7的系数=a\[2\]\*a\[1\]\*a\[0\]；

q=10时，x^10的系数=a\[3\]\*a\[1\]；

这些得到的系数就是题目要求的答案呀~

还有个坑，就是用C语言的printf输出死活都是WA，一改成C++的cin就AC了，估计是long long的格式控制问题吧。。

(⊙v⊙)嗯发现了，我在山理工的oj下提交这道题long long 不能用%I64d，用%lld就能过了~

下面上代码：

/*
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院
    * All rights reserved.
    * 文件名称：number.cpp
    * 作    者：单昕昕
    * 完成日期：2016年4月12日
    * 版 本 号：v1.0
    */
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <time.h>
    #include <stdlib.h>
    using namespace std;
    int a[51];//a0~an-1
    long long ans,p;
    int main()
    {
        int t,i,n,q;
        cin>>t;
        while(t--)
        {
            cin>>n;
            for(i=0; i<n; ++i)
                cin>>a[i];
            cin>>q;
            while(q--)
            {
                i=0;
                ans=1;
                cin>>p;
                while(p)
                {
                    //注意！！当此n下无指数p时，即位数超出n
                    if(i>=n)
                    {
                        ans=0;
                        break;
                    }//下面是一个类似于转换二进制的过程
                    if(p%2)
                        ans=(ans*a[i])%2012;
                    ++i;
                    p/=2;
                }
                cout<<ans<<endl;
            }
        }
        return 0;
    }