第4回acm F題(Alice and Bob)(巧みにバイナリを使う)

タイトル接続:http://acm.upc.edu.cn/problem.php?cid=1109&pid=5
こんな(a 0*x^(2^0)+1)*(a 1*x^(2^1)+1)*.......*(an-1*x^(2^(n-1))+1)多項式、各多項式の係数aはユーザが入力し、項数nもユーザが入力し、次にq行のpを入力し、x^pを示す、x^pの係数mod 2012を出力してください
まずこれは多項式を直接展開しないでください.複雑度は2^nで、タイムアウトして保存できません.
係数PはAi*x^(2^i)+1の2^iからなり、Pを2進数の数と見なすことができ、Pはバイナリの1の位置に対応してaiという位置を表すために用いられ、このPを構成することができる
また,ここではPという数のバイナリのビット数がnを超えているか否かを判断し,i>=nであればans=0である.

#include<stdio.h>
#include<string.h>
#define mod 2012
int main()
{
    long long p;
    int a[55],n,i,q;
    int t;
    int flag;
    int ans;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(0));
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        scanf("%d",&q);
        while(q--)
        {
            ans=1;i=0;
            flag=1;
            scanf("%lld",&p);
            while(p)
            {
                if(i>=n)
                {
                    ans=0;break;
                }
                if(p%2==1)
                {
                    ans*=a[i];
                    ans%=mod;
                }
                i++;
                p/=2;
            }
            printf("%d
",ans);

        }
    }
    return 0;
}