提交记录 38828


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_dsh_260814 1002. 测测你的多项式乘法 Accepted 100 49.126 ms 41616 KB C++ 16.64 KB
提交时间 评测时间
2026-08-15 07:31:43 2026-08-15 07:31:46
// NTT mod 998244353, radix-8 DIF/DIT, all-Montgomery AVX2, INTERLEAVED twiddles
// (w1..w7 for each 8-point block stored contiguously -> single stream).
#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")
#include <immintrin.h>
typedef unsigned long long u64;
typedef unsigned int u32;
const u32 MOD=998244353u, NINV=998244351u, R2=932051910u, G=3u;
const u32 IM=911660635u, IINV=MOD-911660635u;
const int MAXN=1<<21;
alignas(32) static u32 a[MAXN], b[MAXN];
alignas(32) static u32 tw[MAXN+64], twi[MAXN+64];
alignas(32) static u32 tmp[MAXN/8+8];

static inline u32 modpow(u32 base,u64 e){u64 r=1,bb=base%MOD;for(;e;e>>=1){if(e&1)r=r*bb%MOD;bb=bb*bb%MOD;}return (u32)r;}
static inline u32 mont_s(u32 a,u32 b){u64 t=(u64)a*b;u32 m=(u32)t*NINV;u32 u=(u32)((t+(u64)m*MOD)>>32);if(u>=MOD)u-=MOD;return u;}
static inline u32 add_s(u32 a,u32 b){u32 s=a+b; return s>=MOD? s-MOD:s;}
static inline u32 sub_s(u32 a,u32 b){u32 d=a-b; return (int)d<0? d+MOD:d;}

static inline __m256i mont8(__m256i x,__m256i y,const __m256i&ninv,const __m256i&modv,const __m256i&shuf){
    __m256i t_lo=_mm256_mullo_epi32(x,y);
    __m256i m=_mm256_mullo_epi32(t_lo,ninv);
    __m256i pe=_mm256_mul_epu32(x,y);
    __m256i po=_mm256_mul_epu32(_mm256_srli_epi64(x,32),_mm256_srli_epi64(y,32));
    __m256i me=_mm256_mul_epu32(m,modv);
    __m256i mo=_mm256_mul_epu32(_mm256_srli_epi64(m,32),modv);
    __m256i ue=_mm256_srli_epi64(_mm256_add_epi64(pe,me),32);
    __m256i uo=_mm256_srli_epi64(_mm256_add_epi64(po,mo),32);
    __m256i e=_mm256_shuffle_epi8(ue,shuf);
    __m256i o=_mm256_shuffle_epi8(uo,shuf);
    __m256i u=_mm256_unpacklo_epi32(e,o);
    u=_mm256_min_epu32(u,_mm256_sub_epi32(u,modv));
    return u;
}
// mont with precomputed yn = y*NINV mod 2^32 (saves one vpmulld); used for the constant internal twiddles only.
static inline __m256i mont8n(__m256i x,__m256i y,__m256i yn,const __m256i&modv,const __m256i&shuf){
    __m256i m=_mm256_mullo_epi32(x,yn);
    __m256i pe=_mm256_mul_epu32(x,y);
    __m256i po=_mm256_mul_epu32(_mm256_srli_epi64(x,32),_mm256_srli_epi64(y,32));
    __m256i me=_mm256_mul_epu32(m,modv);
    __m256i mo=_mm256_mul_epu32(_mm256_srli_epi64(m,32),modv);
    __m256i ue=_mm256_srli_epi64(_mm256_add_epi64(pe,me),32);
    __m256i uo=_mm256_srli_epi64(_mm256_add_epi64(po,mo),32);
    __m256i e=_mm256_shuffle_epi8(ue,shuf);
    __m256i o=_mm256_shuffle_epi8(uo,shuf);
    __m256i u=_mm256_unpacklo_epi32(e,o);
    u=_mm256_min_epu32(u,_mm256_sub_epi32(u,modv));
    return u;
}
static inline __m256i addm(__m256i a,__m256i b,const __m256i&modv){__m256i s=_mm256_add_epi32(a,b);return _mm256_min_epu32(s,_mm256_sub_epi32(s,modv));}
static inline __m256i subm(__m256i a,__m256i b,const __m256i&modv){__m256i d=_mm256_sub_epi32(a,b);return _mm256_min_epu32(d,_mm256_add_epi32(d,modv));}

static void dif8(u32*x,int n,const u32*tw,u32 Z1,u32 Z3,u32 Iv,u32 Z1n,u32 Z3n,u32 Ivn){
    const __m256i ninv=_mm256_set1_epi32(NINV),modv=_mm256_set1_epi32(MOD);
    const __m256i shuf=_mm256_setr_epi8(0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0, 0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0);
    const __m256i z1=_mm256_set1_epi32(Z1),z3=_mm256_set1_epi32(Z3),iv=_mm256_set1_epi32(Iv);
    const __m256i z1n=_mm256_set1_epi32(Z1n),z3n=_mm256_set1_epi32(Z3n),ivn=_mm256_set1_epi32(Ivn);
    int off=0;
    for(int len=n;len>8;len>>=3){int s=len>>3;
        for(int i=0;i<n;i+=len){u32*y=x+i;int p=0;
            for(;p+8<=s;p+=8){
                __m256i x0=_mm256_loadu_si256((__m256i*)(y+p));
                __m256i x1=_mm256_loadu_si256((__m256i*)(y+p+s));
                __m256i x2=_mm256_loadu_si256((__m256i*)(y+p+2*s));
                __m256i x3=_mm256_loadu_si256((__m256i*)(y+p+3*s));
                __m256i x4=_mm256_loadu_si256((__m256i*)(y+p+4*s));
                __m256i x5=_mm256_loadu_si256((__m256i*)(y+p+5*s));
                __m256i x6=_mm256_loadu_si256((__m256i*)(y+p+6*s));
                __m256i x7=_mm256_loadu_si256((__m256i*)(y+p+7*s));
                const u32* wb=tw+off+p*7;
                __m256i w1=_mm256_loadu_si256((__m256i*)(wb+0));
                __m256i w2=_mm256_loadu_si256((__m256i*)(wb+8));
                __m256i w3=_mm256_loadu_si256((__m256i*)(wb+16));
                __m256i w4=_mm256_loadu_si256((__m256i*)(wb+24));
                __m256i w5=_mm256_loadu_si256((__m256i*)(wb+32));
                __m256i w6=_mm256_loadu_si256((__m256i*)(wb+40));
                __m256i w7=_mm256_loadu_si256((__m256i*)(wb+48));
                __m256i d0=addm(x0,x4,modv),d1=addm(x1,x5,modv),d2=addm(x2,x6,modv),d3=addm(x3,x7,modv);
                __m256i e0=subm(x0,x4,modv);
                __m256i e1=mont8n(subm(x1,x5,modv),z1,z1n,modv,shuf);
                __m256i e2=mont8n(subm(x2,x6,modv),iv,ivn,modv,shuf);
                __m256i e3=mont8n(subm(x3,x7,modv),z3,z3n,modv,shuf);
                __m256i s02=addm(d0,d2,modv),t02=subm(d0,d2,modv);
                __m256i s13=addm(d1,d3,modv),t13=mont8n(subm(d1,d3,modv),iv,ivn,modv,shuf);
                __m256i D0=addm(s02,s13,modv),D2=subm(s02,s13,modv);
                __m256i D1=addm(t02,t13,modv),D3=subm(t02,t13,modv);
                __m256i u02=addm(e0,e2,modv),v02=subm(e0,e2,modv);
                __m256i u13=addm(e1,e3,modv),v13=mont8n(subm(e1,e3,modv),iv,ivn,modv,shuf);
                __m256i E0=addm(u02,u13,modv),E2=subm(u02,u13,modv);
                __m256i E1=addm(v02,v13,modv),E3=subm(v02,v13,modv);
                _mm256_storeu_si256((__m256i*)(y+p),D0);
                _mm256_storeu_si256((__m256i*)(y+p+s),mont8(E0,w1,ninv,modv,shuf));
                _mm256_storeu_si256((__m256i*)(y+p+2*s),mont8(D1,w2,ninv,modv,shuf));
                _mm256_storeu_si256((__m256i*)(y+p+3*s),mont8(E1,w3,ninv,modv,shuf));
                _mm256_storeu_si256((__m256i*)(y+p+4*s),mont8(D2,w4,ninv,modv,shuf));
                _mm256_storeu_si256((__m256i*)(y+p+5*s),mont8(E2,w5,ninv,modv,shuf));
                _mm256_storeu_si256((__m256i*)(y+p+6*s),mont8(D3,w6,ninv,modv,shuf));
                _mm256_storeu_si256((__m256i*)(y+p+7*s),mont8(E3,w7,ninv,modv,shuf));
            }
            for(;p<s;p++){
                u32 x0=y[p],x1=y[p+s],x2=y[p+2*s],x3=y[p+3*s],x4=y[p+4*s],x5=y[p+5*s],x6=y[p+6*s],x7=y[p+7*s];
                const u32* wb=tw+off+p*7;
                u32 d0=add_s(x0,x4),d1=add_s(x1,x5),d2=add_s(x2,x6),d3=add_s(x3,x7);
                u32 e0=sub_s(x0,x4),e1=mont_s(sub_s(x1,x5),Z1),e2=mont_s(sub_s(x2,x6),Iv),e3=mont_s(sub_s(x3,x7),Z3);
                u32 s02=add_s(d0,d2),t02=sub_s(d0,d2);
                u32 s13=add_s(d1,d3),t13=mont_s(sub_s(d1,d3),Iv);
                u32 D0=add_s(s02,s13),D2=sub_s(s02,s13);
                u32 D1=add_s(t02,t13),D3=sub_s(t02,t13);
                u32 u02=add_s(e0,e2),v02=sub_s(e0,e2);
                u32 u13=add_s(e1,e3),v13=mont_s(sub_s(e1,e3),Iv);
                u32 E0=add_s(u02,u13),E2=sub_s(u02,u13);
                u32 E1=add_s(v02,v13),E3=sub_s(v02,v13);
                y[p]=D0;
                y[p+s]=mont_s(E0,wb[0]);
                y[p+2*s]=mont_s(D1,wb[8]);
                y[p+3*s]=mont_s(E1,wb[16]);
                y[p+4*s]=mont_s(D2,wb[24]);
                y[p+5*s]=mont_s(E2,wb[32]);
                y[p+6*s]=mont_s(D3,wb[40]);
                y[p+7*s]=mont_s(E3,wb[48]);
            }
        }
        off+=7*s;
    }
    for(int i=0;i+8<=n;i+=8){u32*Y=x+i;
        u32 x0=Y[0],x1=Y[1],x2=Y[2],x3=Y[3],x4=Y[4],x5=Y[5],x6=Y[6],x7=Y[7];
        u32 d0=add_s(x0,x4),d1=add_s(x1,x5),d2=add_s(x2,x6),d3=add_s(x3,x7);
        u32 e0=sub_s(x0,x4),e1=mont_s(sub_s(x1,x5),Z1),e2=mont_s(sub_s(x2,x6),Iv),e3=mont_s(sub_s(x3,x7),Z3);
        u32 s02=add_s(d0,d2),t02=sub_s(d0,d2),s13=add_s(d1,d3),t13=mont_s(sub_s(d1,d3),Iv);
        u32 D0=add_s(s02,s13),D2=sub_s(s02,s13),D1=add_s(t02,t13),D3=sub_s(t02,t13);
        u32 u02=add_s(e0,e2),v02=sub_s(e0,e2),u13=add_s(e1,e3),v13=mont_s(sub_s(e1,e3),Iv);
        u32 E0=add_s(u02,u13),E2=sub_s(u02,u13),E1=add_s(v02,v13),E3=sub_s(v02,v13);
        Y[0]=D0;Y[1]=E0;Y[2]=D1;Y[3]=E1;Y[4]=D2;Y[5]=E2;Y[6]=D3;Y[7]=E3;
    }
}
static void dit8(u32*x,int n,const u32*tw,u32 Z1,u32 Z3,u32 Iv,u32 Z1n,u32 Z3n,u32 Ivn){
    const __m256i ninv=_mm256_set1_epi32(NINV),modv=_mm256_set1_epi32(MOD);
    const __m256i shuf=_mm256_setr_epi8(0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0, 0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0);
    const __m256i z1=_mm256_set1_epi32(Z1),z3=_mm256_set1_epi32(Z3),iv=_mm256_set1_epi32(Iv);
    const __m256i z1n=_mm256_set1_epi32(Z1n),z3n=_mm256_set1_epi32(Z3n),ivn=_mm256_set1_epi32(Ivn);
    for(int i=0;i+8<=n;i+=8){u32*Y=x+i;
        u32 x0=Y[0],x1=Y[1],x2=Y[2],x3=Y[3],x4=Y[4],x5=Y[5],x6=Y[6],x7=Y[7];
        u32 d0=add_s(x0,x4),d1=add_s(x1,x5),d2=add_s(x2,x6),d3=add_s(x3,x7);
        u32 e0=sub_s(x0,x4),e1=mont_s(sub_s(x1,x5),Z1),e2=mont_s(sub_s(x2,x6),Iv),e3=mont_s(sub_s(x3,x7),Z3);
        u32 s02=add_s(d0,d2),t02=sub_s(d0,d2),s13=add_s(d1,d3),t13=mont_s(sub_s(d1,d3),Iv);
        u32 D0=add_s(s02,s13),D2=sub_s(s02,s13),D1=add_s(t02,t13),D3=sub_s(t02,t13);
        u32 u02=add_s(e0,e2),v02=sub_s(e0,e2),u13=add_s(e1,e3),v13=mont_s(sub_s(e1,e3),Iv);
        u32 E0=add_s(u02,u13),E2=sub_s(u02,u13),E1=add_s(v02,v13),E3=sub_s(v02,v13);
        Y[0]=D0;Y[1]=E0;Y[2]=D1;Y[3]=E1;Y[4]=D2;Y[5]=E2;Y[6]=D3;Y[7]=E3;
    }
    int off=7;
    for(int len=64;len<=n;len<<=3){int s=len>>3;
        for(int i=0;i<n;i+=len){u32*y=x+i;int p=0;
            for(;p+8<=s;p+=8){
                const u32* wb=tw+off+p*7;
                __m256i x0=_mm256_loadu_si256((__m256i*)(y+p));
                __m256i x1=mont8(_mm256_loadu_si256((__m256i*)(y+p+s)),_mm256_loadu_si256((__m256i*)(wb+0)),ninv,modv,shuf);
                __m256i x2=mont8(_mm256_loadu_si256((__m256i*)(y+p+2*s)),_mm256_loadu_si256((__m256i*)(wb+8)),ninv,modv,shuf);
                __m256i x3=mont8(_mm256_loadu_si256((__m256i*)(y+p+3*s)),_mm256_loadu_si256((__m256i*)(wb+16)),ninv,modv,shuf);
                __m256i x4=mont8(_mm256_loadu_si256((__m256i*)(y+p+4*s)),_mm256_loadu_si256((__m256i*)(wb+24)),ninv,modv,shuf);
                __m256i x5=mont8(_mm256_loadu_si256((__m256i*)(y+p+5*s)),_mm256_loadu_si256((__m256i*)(wb+32)),ninv,modv,shuf);
                __m256i x6=mont8(_mm256_loadu_si256((__m256i*)(y+p+6*s)),_mm256_loadu_si256((__m256i*)(wb+40)),ninv,modv,shuf);
                __m256i x7=mont8(_mm256_loadu_si256((__m256i*)(y+p+7*s)),_mm256_loadu_si256((__m256i*)(wb+48)),ninv,modv,shuf);
                __m256i d0=addm(x0,x4,modv),d1=addm(x1,x5,modv),d2=addm(x2,x6,modv),d3=addm(x3,x7,modv);
                __m256i e0=subm(x0,x4,modv);
                __m256i e1=mont8n(subm(x1,x5,modv),z1,z1n,modv,shuf);
                __m256i e2=mont8n(subm(x2,x6,modv),iv,ivn,modv,shuf);
                __m256i e3=mont8n(subm(x3,x7,modv),z3,z3n,modv,shuf);
                __m256i s02=addm(d0,d2,modv),t02=subm(d0,d2,modv);
                __m256i s13=addm(d1,d3,modv),t13=mont8n(subm(d1,d3,modv),iv,ivn,modv,shuf);
                __m256i D0=addm(s02,s13,modv),D2=subm(s02,s13,modv);
                __m256i D1=addm(t02,t13,modv),D3=subm(t02,t13,modv);
                __m256i u02=addm(e0,e2,modv),v02=subm(e0,e2,modv);
                __m256i u13=addm(e1,e3,modv),v13=mont8n(subm(e1,e3,modv),iv,ivn,modv,shuf);
                __m256i E0=addm(u02,u13,modv),E2=subm(u02,u13,modv);
                __m256i E1=addm(v02,v13,modv),E3=subm(v02,v13,modv);
                _mm256_storeu_si256((__m256i*)(y+p),D0);
                _mm256_storeu_si256((__m256i*)(y+p+s),E0);
                _mm256_storeu_si256((__m256i*)(y+p+2*s),D1);
                _mm256_storeu_si256((__m256i*)(y+p+3*s),E1);
                _mm256_storeu_si256((__m256i*)(y+p+4*s),D2);
                _mm256_storeu_si256((__m256i*)(y+p+5*s),E2);
                _mm256_storeu_si256((__m256i*)(y+p+6*s),D3);
                _mm256_storeu_si256((__m256i*)(y+p+7*s),E3);
            }
            for(;p<s;p++){
                u32 x0=y[p],x1=mont_s(y[p+s],tw[off+p*7+0]),x2=mont_s(y[p+2*s],tw[off+p*7+8]),x3=mont_s(y[p+3*s],tw[off+p*7+16]);
                u32 x4=mont_s(y[p+4*s],tw[off+p*7+24]),x5=mont_s(y[p+5*s],tw[off+p*7+32]),x6=mont_s(y[p+6*s],tw[off+p*7+40]),x7=mont_s(y[p+7*s],tw[off+p*7+48]);
                u32 d0=add_s(x0,x4),d1=add_s(x1,x5),d2=add_s(x2,x6),d3=add_s(x3,x7);
                u32 e0=sub_s(x0,x4),e1=mont_s(sub_s(x1,x5),Z1),e2=mont_s(sub_s(x2,x6),Iv),e3=mont_s(sub_s(x3,x7),Z3);
                u32 s02=add_s(d0,d2),t02=sub_s(d0,d2);
                u32 s13=add_s(d1,d3),t13=mont_s(sub_s(d1,d3),Iv);
                u32 D0=add_s(s02,s13),D2=sub_s(s02,s13);
                u32 D1=add_s(t02,t13),D3=sub_s(t02,t13);
                u32 u02=add_s(e0,e2),v02=sub_s(e0,e2);
                u32 u13=add_s(e1,e3),v13=mont_s(sub_s(e1,e3),Iv);
                u32 E0=add_s(u02,u13),E2=sub_s(u02,u13);
                u32 E1=add_s(v02,v13),E3=sub_s(v02,v13);
                y[p]=D0;y[p+s]=E0;y[p+2*s]=D1;y[p+3*s]=E1;y[p+4*s]=D2;y[p+5*s]=E2;y[p+6*s]=D3;y[p+7*s]=E3;
            }
        }
        off+=7*s;
    }
}

void poly_multiply(unsigned *A, int n, unsigned *B, int m, unsigned *c) {
    int size=1; while(size<n+m+1)size<<=1;
    {int s=size,lg=0;while(s>1){s>>=1;lg++;}while(lg%3)size<<=1,lg++;} // pad to power of 8
    u32 ninv_scale=modpow((u32)size,MOD-2);
    u32 md[10], mda[10];
    for(int i=0;i<10;i++){md[i]=mont_s((u32)i,R2); mda[i]=(u32)(((u64)i*ninv_scale)%MOD);}
    int i=0;
    for(i=0;i<=n;i++)a[i]=mda[A[i]];
    for(;i<size;i++)a[i]=0;
    for(i=0;i<=m;i++)b[i]=md[B[i]];
    for(;i<size;i++)b[i]=0;
    u32 w=modpow(G,(MOD-1)/(u32)size), iw=modpow(w,MOD-2);
    u32 Z1=mont_s(modpow(w,(u32)(size/8)),R2), Z3=mont_s(modpow(w,3u*(u32)(size/8)),R2), Iv=mont_s(IM,R2);
    u32 Z1i=mont_s(modpow(iw,(u32)(size/8)),R2), Z3i=mont_s(modpow(iw,3u*(u32)(size/8)),R2), Ivi=mont_s(IINV,R2);
    u32 Z1n=(u32)((u64)Z1*NINV), Z3n=(u32)((u64)Z3*NINV), Ivn=(u32)((u64)Iv*NINV);
    u32 Z1in=(u32)((u64)Z1i*NINV), Z3in=(u32)((u64)Z3i*NINV), Ivin=(u32)((u64)Ivi*NINV);
    // forward twiddles (interleaved)
    {const __m256i ninv=_mm256_set1_epi32(NINV),modv=_mm256_set1_epi32(MOD);
     const __m256i shuf=_mm256_setr_epi8(0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0, 0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0);
     int off=0;
     for(int len=size;len>=8;len>>=3){int s=len>>3,step=size/len;
       u32 ws=modpow(w,(u64)step); u32 wm=mont_s(ws,R2);
       tmp[0]=mont_s(1,R2);
       for(int p=1;p<s;p++) tmp[p]=mont_s(tmp[p-1],wm);
       for(int p=0;p<s;p+=8){
         __m256i t1=_mm256_loadu_si256((__m256i*)(tmp+p));
         __m256i t2=mont8(t1,t1,ninv,modv,shuf);
         __m256i t3=mont8(t2,t1,ninv,modv,shuf);
         __m256i t4=mont8(t3,t1,ninv,modv,shuf);
         __m256i t5=mont8(t4,t1,ninv,modv,shuf);
         __m256i t6=mont8(t5,t1,ninv,modv,shuf);
         __m256i t7=mont8(t6,t1,ninv,modv,shuf);
         u32* wb=tw+off+p*7;
         _mm256_storeu_si256((__m256i*)(wb+0),t1);
         _mm256_storeu_si256((__m256i*)(wb+8),t2);
         _mm256_storeu_si256((__m256i*)(wb+16),t3);
         _mm256_storeu_si256((__m256i*)(wb+24),t4);
         _mm256_storeu_si256((__m256i*)(wb+32),t5);
         _mm256_storeu_si256((__m256i*)(wb+40),t6);
         _mm256_storeu_si256((__m256i*)(wb+48),t7);}
       off+=7*s;}}
    // inverse twiddles (interleaved)
    {const __m256i ninv=_mm256_set1_epi32(NINV),modv=_mm256_set1_epi32(MOD);
     const __m256i shuf=_mm256_setr_epi8(0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0, 0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0);
     int off=0;
     for(int len=8;len<=size;len<<=3){int s=len>>3,step=size/len;
       u32 ws=modpow(iw,(u64)step); u32 wm=mont_s(ws,R2);
       tmp[0]=mont_s(1,R2);
       for(int p=1;p<s;p++) tmp[p]=mont_s(tmp[p-1],wm);
       for(int p=0;p<s;p+=8){
         __m256i t1=_mm256_loadu_si256((__m256i*)(tmp+p));
         __m256i t2=mont8(t1,t1,ninv,modv,shuf);
         __m256i t3=mont8(t2,t1,ninv,modv,shuf);
         __m256i t4=mont8(t3,t1,ninv,modv,shuf);
         __m256i t5=mont8(t4,t1,ninv,modv,shuf);
         __m256i t6=mont8(t5,t1,ninv,modv,shuf);
         __m256i t7=mont8(t6,t1,ninv,modv,shuf);
         u32* wb=twi+off+p*7;
         _mm256_storeu_si256((__m256i*)(wb+0),t1);
         _mm256_storeu_si256((__m256i*)(wb+8),t2);
         _mm256_storeu_si256((__m256i*)(wb+16),t3);
         _mm256_storeu_si256((__m256i*)(wb+24),t4);
         _mm256_storeu_si256((__m256i*)(wb+32),t5);
         _mm256_storeu_si256((__m256i*)(wb+40),t6);
         _mm256_storeu_si256((__m256i*)(wb+48),t7);}
       off+=7*s;}}
    dif8(a,size,tw,Z1,Z3,Iv,Z1n,Z3n,Ivn);
    dif8(b,size,tw,Z1,Z3,Iv,Z1n,Z3n,Ivn);
    {const __m256i ninv=_mm256_set1_epi32(NINV),modv=_mm256_set1_epi32(MOD);
     const __m256i shuf=_mm256_setr_epi8(0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0, 0,1,2,3,8,9,10,11,0,0,0,0,0,0,0,0);
     for(int i=0;i<size;i+=8){__m256i x=_mm256_loadu_si256((__m256i*)(a+i));__m256i y=_mm256_loadu_si256((__m256i*)(b+i));_mm256_storeu_si256((__m256i*)(a+i),mont8(x,y,ninv,modv,shuf));}}
    dit8(a,size,twi,Z1i,Z3i,Ivi,Z1in,Z3in,Ivin);
    int outn=n+m+1;
    for(int i=0;i<outn;i++) c[i]=a[i];
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #149.126 ms40 MB + 656 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-09-05 00:58:16 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠