sdutoj 2608 Alice and Bob

时间:2023-03-09 03:11:10
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.

示例输入

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

示例程序

分析:

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代码:

 #include<stdio.h>
#include<string.h>
int a[],b[];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,p,i,j;
scanf("%d",&n);
memset(a,,sizeof(a));
for(i=;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&p);
int count,ans;
long long c;
while(p--)
{
count=,ans=;
scanf("%lld",&c);
if(c==)
{
printf("1\n");
continue;
} while(c)
{
b[ans++]=c%;
c/=;
}
for(i=;i<ans;i++)
if(b[i])
{
count=count*a[i]%;
}
printf("%d\n",count);
}
}
return ;
}

官方标程:

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = ;
int a[], n;
int Q;
#define ll long long
ll w[];
#define fuck while(1)
int main() {
int t;
freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
scanf("%d", &t);
w[] = ;
for(int i = ; i < ; i++) w[i] = (w[i - ] << );
while(t--) {
scanf("%d", &n);
if(n <= || n > ) fuck;
memset(a, , sizeof(a));
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
if(a[i] < || a[i] > ) fuck;
}
scanf("%d", &Q);
while(Q--) {
ll x;
scanf("%I64d", &x);
if(x > 1234567898765432ll) fuck;
int ret = ;
for(int i = ; x; i++, x /= ) {
if((x & )) {
ret = ret * a[i] % mod;
}
}
printf("%d\n", ret);
}
}
return ;
}

数据生成程序:

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <time.h>
using namespace std;
#define ll long long
#define mod 1234567898765432ll
ll r() {
ll a = rand();
a *= rand();
a %= ;
if(a < ) a += ;
return a;
}
ll maxx;
ll rr() {
int xx = rand() % ;
if(xx == ) return ;
return r() * r() % maxx;
}
int main() {
int t = ;
freopen("data.in", "w", stdout);
cout<<t<<endl;
srand(time(NULL));
while(t--) {
int n = rand() % + ;
cout<<n<<endl;
for(int i = ; i < n; i++) {
int a = rand() % ;
if(i) cout<<" ";
cout<<a;
}
maxx = (1ll << (n));
maxx = maxx + maxx / ;
cout<<endl;
int Q = rand() % + ;
ll woca = (1ll << n);
Q = Q % woca + ;
cout<<Q<<endl;
while(Q--) {
cout<<rr() % mod<<endl;
}
}
return ;
}