51nod 1348 乘积之和

用(r-l+2)维向量f[l,r]表示区间[l,r]内选i个数(0<=i<=r-l+1)相乘的所有方案之和，可以发现f[l,r]=f[l,m]*f[m+1,r]，题目模数100003较小，每次卷积后答案上界大约为1e16，用ntt在两个1e9左右的模数下计算后CRT合并即可，复杂度为O(nlogn)，要注意常数优化

#include<cstdio>

#include<cstring>

#include<algorithm>

typedef long long i64;

int _(){

    int x=,f=,c=getchar();

    while(c<)c=='-'&&(f=-),c=getchar();

    while(c>)x=x*+c-,c=getchar();

    return x*f;

}

int pow(int a,int n,int p){

    int v=;

    for(;n;n>>=){

        if(n&)v=i64(v)*a%p;

        a=i64(a)*a%p;

    }

    return v;

}

i64 mul(i64 a,i64 b,i64 p){

    i64 s=;

    a%=p;b%=p;

    while(b){

        if(b&)(s+=a)%=p;

        (a<<=)%=p;

        b>>=;

    }

    return s;

}

int N,X,r[];

template<const int p,const int g>

void ntt(int*a,int t){

    for(int i=;i<N;++i)if(i>r[i])std::swap(a[i],a[r[i]]);

    for(int i=;i<N;i<<=){

        int w=pow(g,(t*(p-)/(i*)+p-),p);

        for(int j=;j<N;j+=i<<){

            int e=,*b=a+j,*c=b+i;

            for(int k=;k<i;++k,e=i64(e)*w%p){

                int x=b[k],y=c[k]*i64(e)%p;

                b[k]=(x+y)%p;

                c[k]=(x-y+p)%p;

            }

        }

    }

    if(t==-){

        i64 I=pow(N,p-,p);

        for(int i=;i<N;++i)a[i]=a[i]*I%p;

    }

}

int n,q,v0[],mem[*+],*mp=mem,vs[][+];

const int p1=,g1=,p2=,g2=;

const i64 m1=i64(p1)*pow(p1,p2-,p2),m2=i64(p2)*pow(p2,p1-,p1),ps=i64(p1)*p2;

int*calc(int L,int R){

    int*pos=mp;mp+=R-L+;

    if(L==R){

        *pos=v0[L];

        return pos;

    }

    int M=L+R>>;

    int*lp=calc(L,M)-;

    int*rp=calc(M+,R)-;

    for(N=,X=;N<R-L+;N<<=,++X);

    if(R-L+<=){

        for(int i=;i<;++i)memset(vs[i],,N*sizeof(int)),vs[i][]=;

        for(int i=;i<=M-L+;++i)vs[][i]=lp[i];

        for(int i=;i<=R-M;++i)vs[][i]=rp[i];

        for(int i=;i<=R-L+;++i){

            for(int j=;j<=i;++j)pos[i-]=(pos[i-]+i64(vs[][j])*vs[][i-j])%;

        }

        return pos;

    }

    for(int i=;i<N;++i)r[i]=r[i>>]>>|(i&)<<X;

    for(int i=;i<;++i)memset(vs[i],,N*sizeof(int)),vs[i][]=;

    for(int i=;i<=M-L+;++i)vs[][i]=vs[][i]=lp[i];

    for(int i=;i<=R-M;++i)vs[][i]=vs[][i]=rp[i];

    ntt<p1,g1>(vs[],);

    ntt<p1,g1>(vs[],);

    ntt<p2,g2>(vs[],);

    ntt<p2,g2>(vs[],);

    for(int i=;i<N;++i)vs[][i]=i64(vs[][i])*vs[][i]%p1;

    for(int i=;i<N;++i)vs[][i]=i64(vs[][i])*vs[][i]%p2;

    ntt<p1,g1>(vs[],-);

    ntt<p2,g2>(vs[],-);

    for(int i=;i<=R-L+;++i)pos[i-]=(mul(m2,vs[][i],ps)+mul(m1,vs[][i],ps))%ps%;

    return pos;

}

int main(){

    n=_();q=_();

    for(int i=;i<=n;++i)v0[i]=_();

    int*ans=calc(,n)-;

    while(q--)printf("%d\n",ans[_()]);

    return ;

}