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?
输入
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
输出
示例输入
1
2
2 1
2
3
4
示例输出
2
0
提示
来源
示例程序
分析：
给出一个多项式：(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 ;
}