2016北京集训 小Q与进位制

题目大意

一个数每一位进制不同，已知每一位的进制，求该数的十进制表达。

显然有

$$Ans=\sum\limits_{i=0}^{n-1}a_i \prod\limits_{j=0}^{i-1}base_j$$

若不考虑高精度则线性复杂度内由低位向高位递推即可，但考虑高精度的话即使压位也会$TLE$。

采用分治$+FFT$加速运算的方法。

分别求出第$1$至第$\frac n2$位和第$\frac n2+1$至第$n$位的答案，顺便求出$\prod\limits_{i=0}^{\frac n2}base_i$。

简单的两数相加提取公因数即可。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 370020

#define MAXN 1000

#define MLEN 10000000ll

const double PI=acos(-1);

using namespace std;

LL read(){

    LL nm=0,fh=1; char cw=getchar();

    for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;

    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');

    return nm*fh;

}

void write(LL x){if(x>9) write(x/10);putchar(x%10+'0');}

struct comp{

    double r,d;

    comp(){r=d=0;}

    comp(double _r,double _d){r=_r,d=_d;}

    comp operator+ (const comp & ot)const{return comp(r+ot.r,d+ot.d);}

    comp operator- (const comp & ot)const{return comp(r-ot.r,d-ot.d);}

    comp operator* (const comp & ot)const{return comp(r*ot.r-d*ot.d,r*ot.d+d*ot.r);}

}tt1[M],tt2[M];

int od[M],lg[M];

void FFT(comp *x,int len,double kd){

    for(int i=0;i<len;i++) if(i<od[i]) swap(x[i],x[od[i]]);

    for(LL tt=1;tt<len;tt<<=1){

        comp unit(cos(PI*kd/(tt*1.0)),sin(PI*kd/(tt*1.0))),now;

        for(LL pos,st=0;st<len;st+=(tt<<1)){

            for(now=comp(1.0,0.0),pos=st;pos<st+tt;pos++,now=now*unit){

                comp t1=x[pos],t2=now*x[pos+tt]; x[pos]=t1+t2,x[pos+tt]=t1-t2;

            }

        }

    }

    if(kd<0.0){for(LL i=0;i<len;i++) x[i].r/=(len*1.0);}

}

void opt(LL *x,LL len){

    for(len--,write(x[len]);len--;){

        if(x[len]<100) putchar('0');

        if(x[len]<10) putchar('0');

        write(x[len]);

    }

    putchar('\n');

}

LL mul(LL *x,LL *T1,LL *T2,LL n1,LL n2){

    LL len=(1ll<<lg[n1+n2]),N=n1+n2-1; x[N]=x[N+1]=0;

    if(n1+n2<=1024){

        for(int i=0;i<=n1+n2+2;i++) x[i]=0ll;

        for(int i=0;i<n1;i++) for(int j=0;j<n2;j++) x[i+j]+=T1[i]*T2[j];

    }

    else{

    	for(int i=1;i<len;i++) od[i]=(od[i>>1]>>1)|((i&1)<<(lg[len]-2));

        for(int i=0;i<n1;i++) tt1[i]=comp(T1[i],0);

        for(int i=0;i<n2;i++) tt2[i]=comp(T2[i],0);

        for(int i=n1;i<len;i++) tt1[i]=comp(0,0);

        for(int i=n2;i<len;i++) tt2[i]=comp(0,0);

        FFT(tt1,len,1.0),FFT(tt2,len,1.0);

        for(int i=0;i<len;i++) tt1[i]=tt1[i]*tt2[i]; FFT(tt1,len,-1.0);

        for(int i=0;i<len;i++) x[i]=floor(tt1[i].r+0.5);

    }

    for(int i=0;i<N;i++) x[i+1]+=x[i]/MAXN,x[i]%=MAXN;

    while(x[N]>0) N++,x[N]=x[N-1]/MAXN,x[N-1]%=MAXN; return N;

}

LL add(LL *x,LL *x1,LL *x2,LL n1,LL n2){

    if(n1>n2) return add(x,x2,x1,n2,n1);

    LL N=n2; x[N]=x[N+1]=0;

    for(LL i=0;i<N;i++) x[i]=x2[i]+(i>=n1?0:x1[i]);

    for(LL i=0;i<N;i++) x[i+1]+=x[i]/MAXN,x[i]%=MAXN;

    while(x[N]) N++,x[N]=x[N-1]/MAXN,x[N-1]%=MAXN; return N;

}

LL n,m,Len,Bs[M],a[M],X[M],A[18][M],B[18][M],AA[18][M],BB[18][M];

LL merge(LL l,LL r,LL kd,LL *x,LL *xx){

    if(r==l){

        LL rm=MLEN+1; x[0]=a[l],xx[0]=Bs[l];

        if(x[0]>=MAXN) x[1]=x[0]/MAXN,x[0]%=MAXN,rm+=MLEN;

        if(xx[0]>=MAXN) xx[1]=xx[0]/MAXN,xx[0]%=MAXN,rm++;

        if(x[1]>=MAXN) x[2]=x[1]/MAXN,x[1]%=MAXN,rm+=MLEN;

        if(xx[1]>=MAXN) xx[2]=xx[1]/MAXN,xx[1]%=MAXN,rm++;

        return rm;

    }

    LL La,lenl=merge(l,((r+l)>>1),kd+1,A[kd+1],AA[kd+1]),la,lb; la=lenl/MLEN,lb=lenl%MLEN;

    LL Lb,lenr=merge(((r+l)>>1)+1,r,kd+1,B[kd+1],BB[kd+1]),ra,rb; ra=lenr/MLEN,rb=lenr%MLEN;

    La=mul(X,AA[kd+1],B[kd+1],lb,ra),La=add(x,A[kd+1],X,la,La);

    if(kd) Lb=mul(xx,AA[kd+1],BB[kd+1],lb,rb); return La*MLEN+Lb;

}

int main(){

    n=read(),lg[0]=-1,Bs[0]=1;

    for(int i=0;i<M;i++) lg[i]=lg[i>>1]+1;

    for(int i=0;i<n;i++) Bs[i]=read();

    for(int i=0;i<n;i++) a[i]=read();

    n=merge(0,n-1,0,A[0],AA[0]),n/=MLEN,opt(A[0],n);return 0;

}