NTT在第810000多位WA,能过样例,求助
查看原帖
NTT在第810000多位WA,能过样例,求助
799772
cxyMOI楼主2023/9/30 21:21
#include <iostream>
#include <string.h>
using namespace std;
#define lint long long
const int p=998244353;
const int w=15311432;
const int invw=469870224;
const int degw=23;
const int logl=20;
const int NTT_l=1<<logl;
const int hl=NTT_l/2;
const int invNTT_l=998243401;
lint h[NTT_l],hh[NTT_l];
#define Q_M(a) ((a)>p)?((a)-p):(a)
void FNTT(lint ww){
    int d,e,f;
    lint x;
    lint a[degw+1];
    a[degw]=ww;
    for(int i=degw-1;i>=0;--i){
        a[i]=(a[i+1]*a[i+1])%p;
    }
    int m;
    for(int n=0;n<logl;n++){
        e=(1<<n)-1;
        f=0;
        for(int k=hl;k<NTT_l;k++){
            if(f!=0){
                d=f;
                x=a[n+1];
                while(d!=1){
                    if(d&1){
                        hh[k]=(hh[k]*x)%p;
                    }
                    x=(x*x)%p;
                    d=(d>>1);
                }
                hh[k]=(x*hh[k])%p;
            }
            if(f==e){
                f=-1;
            }
            f++;
        }
        for(int k=0;k<NTT_l;k++){
            m=((k>>(n+1))<<n)|(k&e);
            if(1&(k>>n)){
                h[k]=Q_M(hh[m]+p-hh[m|hl]);
            }else{
                h[k]=Q_M(hh[m]+hh[m|hl]);
            }
        }
        for(int i=0;i<NTT_l;i++){
            hh[i]=h[i];
        }
    }
}
int sl;
int main(){
    lint a[NTT_l];
    lint b[NTT_l];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    char na[NTT_l];
    char nb[NTT_l];
    scanf("%s%s",na,nb);
    sl=strlen(na)-1;
    for(int i=0; i<=sl;i++){
        a[i]=na[sl-i]-48;
    }
    sl=strlen(nb)-1;
    for(int i=0;i<=sl;i++){
        b[i]=nb[sl-i]-48;
    }
    memset(hh,0,sizeof(hh));
    for(int i=0;i<hl;i++){
        hh[i]=a[i*2]+10*a[i*2+1];
    }
    FNTT(w);
    for(int i=0;i<NTT_l;i++){
        a[i]=hh[i];
    }
    memset(hh,0,sizeof(hh));
    for(int i=0;i<hl;i++){
        hh[i]=b[i*2]+10*b[i*2+1];
    }
    FNTT(w);
    for(int i=0;i<NTT_l;i++){
        b[i]=h[i];
    }
    for(int i=0;i<NTT_l;i++){
        hh[i]=(a[i]*b[i])%p;
    }
    FNTT(invw);
    for(int i=0;i<NTT_l;i++){
        h[i]*=invNTT_l;
        h[i]%=p;
    }
    for(int i=1;i<NTT_l;i++){
        h[i]+=h[i-1]/100;
        h[i-1]%=100;
    }
    int l=0;
    for(int i=NTT_l-1;i>=0;i--){
        if(h[i]==0){
            l++;
        }else{
            break;
        }
    }
    if(l==NTT_l){
        cout<<0;
    }else{
        cout<<h[NTT_l-l-1];
        for(int i=NTT_l-l-2;i>=0;i--){
            cout<<(h[i]/10)<<(h[i]%10);
        }
    }
    return 0;
}

压位NTT

2023/9/30 21:21
加载中...