sdutoj 2608 Alice and Bob

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

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.

示例输入

示例输出

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大学生程序设计竞赛

示例程序

分析：

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

给出一个多项式：(a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1)，输入P，求X^p 前边的系数。

将p转换成一个二进制的数，然后分别乘上系数。

AC代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 int a[55],b[55];
 4 int main()
 5 {
 6     int t;
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         int n,p,i,j;
11         scanf("%d",&n);
12         memset(a,0,sizeof(a));
13         for(i=0;i<n;i++)
14         scanf("%d",&a[i]);
15         scanf("%d",&p);
16         int count,ans;
17         long long c;
18         while(p--)
19         {
20             count=1,ans=0;
21             scanf("%lld",&c);
22             if(c==0)
23             {
24                 printf("1
");
25                 continue;
26             }
27                     
28             while(c)
29             {
30                 b[ans++]=c%2;
31                 c/=2;
32             }
33             for(i=0;i<ans;i++)
34             if(b[i])
35             {
36                 count=count*a[i]%2012;
37             }
38             printf("%d
",count);
39         }
40     }    
41     return 0;
42 }

View Code

官方标程：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 const int mod = 2012;
 8 int a[70], n;
 9 int Q;
10 #define ll long long
11 ll w[60];
12 #define fuck while(1)
13 int main() {
14     int t;
15     freopen("data.in", "r", stdin);
16 //    freopen("data.out", "w", stdout);
17     scanf("%d", &t);
18     w[0] = 1;
19     for(int i = 1; i < 60; i++) w[i] = (w[i - 1] << 1);
20     while(t--) {
21         scanf("%d", &n);
22         if(n <= 0 || n > 50) fuck;
23         memset(a, 0, sizeof(a));
24         for(int i = 0; i < n; i++) {
25             scanf("%d", &a[i]);
26             if(a[i] < 0 || a[i] > 100) fuck;
27         }
28         scanf("%d", &Q);
29         while(Q--) {
30             ll x;
31             scanf("%I64d", &x);
32             if(x > 1234567898765432ll) fuck;
33             int ret = 1;
34             for(int i = 0; x; i++, x /= 2) {
35                 if((x & 1)) {
36                     ret = ret * a[i] % mod;
37                 }
38             }
39             printf("%d
", ret);
40         }
41     }
42     return 0;
43 }

View Code

数据生成程序：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <time.h>
 6 using namespace std;
 7 #define ll long long
 8 #define mod 1234567898765432ll
 9 ll r() {
10     ll a = rand();
11     a *= rand();
12     a %= 100000000;
13     if(a < 0) a += 100000000;
14     return a;
15 }
16 ll maxx;
17 ll rr() {
18     int xx = rand() % 100;
19     if(xx == 0) return 0;
20     return r() * r() % maxx;
21 }
22 int main() {
23     int t = 20;
24     freopen("data.in", "w", stdout);
25     cout<<t<<endl;
26     srand(time(NULL));
27     while(t--) {
28         int n = rand() % 50 + 1;
29         cout<<n<<endl;
30         for(int i = 0; i < n; i++) {
31             int a = rand() % 100;
32             if(i) cout<<" ";
33             cout<<a;
34         }
35         maxx = (1ll << (n));
36         maxx = maxx + maxx / 10000;
37         cout<<endl;
38         int Q = rand() % 1000 + 1;
39         ll woca = (1ll << n);
40         Q = Q % woca + 1;
41         cout<<Q<<endl;
42         while(Q--) {
43             cout<<rr() % mod<<endl;
44         }
45     }
46     return 0;
47 }

View Code