题解 P6828 【任意模数 Chirp Z-Transform】

cyffff · 2021-03-04 13:39:41 · 题解

\text{Link}

板子题，极限卡常差评。

居然没有题解，就来写一篇吧。

upd2021.7.15：修式子和 \LaTeX。

题意

给 n,m,c 和 n-1 次多项式 F(x)，求出 \forall k\in[0,m) F(c^k)。

解法

首先我们有

F(c^k)=\sum_{i=0}^{n-1}a_ic^{ik}

考虑化 ik，

ik=\dfrac{2ik}{2}

=\dfrac{i^2+2ik+k^2-i-k-i^2+i-k^2+k}{2}

=\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}

于是就有

F(c^k)=\sum_{i=0}^{n-1}a_ic^{ik}

=\sum_{i=0}^{n-1}a_ic^{\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}}

=c^{-\binom{k}{2}}\sum_{i=0}^{n-1}a_ic^{-\binom{i}{2}}c^{\binom{i+k}{2}}

可以卷积。

见模数为 998244353 的版本。

模数不对就用 \text{MTT}，时间复杂度 O(n\log n)。

然而这道题还没结束，我们发现了时限 1.23s 空限 345MB，没错，这道题卡时间+卡空间。

下面给出本题卡常的几个技巧：

手动二分数组大小，N=2.1\times 10^6 左右就行了。
预处理单位根幂。
开 double 而不是 long double。
有良好的编码习惯，只在乘法时开 long long，数组开 int，加减法尽量少使用 % 运算。
fread，fwrite 快读快写。
在夜深人静的时候交/多交亿次等评测机波动。

为了方便各位神仙调试，这里给出大部分代码：

#define ll long long
#define ld double
const ld pi=acos(-1);
const int mod=1e9+7,N=2.1e6;
inline void print(int *a){
    for(int i=0;a[i]||a[i+1]||a[i+2]||a[i+3]||a[i+4]||a[i+5];i++){
        printf("%d ",a[i]);
    }
    puts("");
}
struct comp{
    double x,y;
    comp(ld a=0,ld b=0){x=a,y=b;}
    comp neg(){
        return comp(x,-y);
    }
    friend comp operator+(const comp &a,const comp &b){
        return comp(a.x+b.x,a.y+b.y);
    }
    friend comp operator-(const comp &a,const comp &b){
        return comp(a.x-b.x,a.y-b.y);
    }
    friend comp operator*(const comp &a,const comp &b){
        return comp(a.x*b.x-a.y*b.y,a.y*b.x+a.x*b.y);
    }
};
struct ntt{
    comp A[N],B[N],C[N],D[N],qp[N];
    int n,rev[N],f[N],g[N],lim,c[N],ic[N];
    int m,_c;
    inline void init(int n,int mode=1){
        if(mode){
            int l=0;
            for(lim=1;lim<=n;lim<<=1)l++;
            for(int i=1;i<lim;i++){
                rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
            }
            for(int i=1;i<lim;i<<=1){
                for(int j=0;j<i;j++){
                    qp[lim/i*j]=comp(cos(j*pi/i),sin(j*pi/i));
                }
            }
        }else{
            for(lim=1;lim<=n;lim<<=1);
        }
    }
    inline int qpow(int x,int y){
        int res=1;
        while(y){
            if(y&1) res=1ll*res*x%mod;
            x=1ll*x*x%mod;
            y>>=1;
        }
        return res;
    }
    inline void FFT(comp *a,int tpe){
        for(int i=0;i<lim;i++){
            if(i<rev[i]){
                swap(a[i],a[rev[i]]);
            }
        }
        for(int i=1;i<lim;i<<=1){
            for(int j=0;j<lim;j+=(i<<1)){
                for(int k=0;k<i;k++){
                    comp t=a[i+j+k]*(tpe==1?qp[lim/i*k]:qp[lim/i*k].neg());
                    a[i+j+k]=a[j+k]-t;
                    a[j+k]=a[j+k]+t;
                }
            }
        }
    }
    inline void MTT(int *f,int *g,int *ans){
        for(int i=0;i<lim;i++){
            A[i].x=f[i]>>15,A[i].y=f[i]&32767;
            C[i].x=g[i]>>15,C[i].y=g[i]&32767;
        }
        FFT(A,1);
        FFT(C,1);
        for(int i=1;i<lim;i++){
            B[i]=A[lim-i].neg();
        }
        B[0]=A[0].neg();
        for(int i=1;i<lim;i++){
            D[i]=C[lim-i].neg();
        }
        D[0]=C[0].neg();
        for(int i=0;i<lim;i++){
            comp aa=(A[i]+B[i])*comp(0.5,0);
            comp bb=(A[i]-B[i])*comp(0,-0.5);
            comp cc=(C[i]+D[i])*comp(0.5,0);
            comp dd=(C[i]-D[i])*comp(0,-0.5);
            A[i]=aa*cc+comp(0,1)*(aa*dd+bb*cc);
            B[i]=bb*dd;
        }
        FFT(A,-1);
        FFT(B,-1);
        for(int i=0;i<lim;i++){
            int aa=(ll)(A[i].x/lim+0.5)%mod;
            int bb=(ll)(A[i].y/lim+0.5)%mod;
            int cc=(ll)(B[i].x/lim+0.5)%mod;
            ans[i]=((1ll*aa*(1<<30)+1ll*bb*(1<<15)+cc)%mod+mod)%mod;
        }
    }
    inline void MAIN(){
        n=read(),_c=read(),m=read();
        c[0]=ic[0]=1;
        for(int i=1;i<=n+m;i++){
            c[i]=1ll*c[i-1]*_c%mod;
        }
        for(int i=1;i<=n+m;i++){
            c[i]=1ll*c[i-1]*c[i]%mod;
        }
        ic[1]=qpow(_c,mod-2);
        int qq=ic[1];
        for(int i=1;i<=max(n,m);i++){
            ic[i]=1ll*ic[i-1]*qq%mod;
        }
        for(int i=1;i<=max(n,m);i++){
            ic[i]=1ll*ic[i-1]*ic[i]%mod;
        }
        f[0]=read();
        for(int i=1;i<n;i++){
            f[i]=1ll*read()*ic[i-1]%mod;
        }
        init(n+m);
        g[0]=1;
        for(int i=1;i<=n+m;i++){
            g[i]=c[i-1];
        }
        reverse(f,f+n+1);
        MTT(f,g,f);
        for(int i=0;i<m;i++){
            write((long long)f[i+n]*(i?ic[i-1]:1)%mod);
            out[len++]=' ';
        }
    }
}w;

最慢点 1.23s（没错卡常卡到这种程度），最大空间 196.23MB。

希望各位~~卡常愉快~~，早日卡过~。

若有问题请私信/评论。

再见 qwq~