NTT WA0pts求助
查看原帖
NTT WA0pts求助
203008
山田リョウ楼主2022/5/4 23:12
// Problem: P1919 【模板】A*B Problem 升级版(FFT 快速傅里叶变换)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1919
// Memory Limit: 256 MB
// Time Limit: 1500 ms

#include<stdio.h>
#include<ctype.h>
#include<algorithm>
constexpr int p=998244353,g=3;
int rev[2097152],n,m,t,l,A[2097152],B[2097152];
int pow(int b){int ans=1,x=g;for(;b;b>>=1,x=(long long)x*x%p)if(b&1)ans=(long long)ans*x%p;return ans;}
void NTT(int*a,int op){
    for(int i=1;i<t;++i)if(i<rev[i]){int t=a[i];a[i]=a[rev[i]];a[rev[i]]=t;}
    for(int i=1;i<t;i<<=1){
        int wn;
        if(op)wn=pow(p-1-((p-1)/(i<<1)));
        else wn=pow((p-1)/(i<<1));
        for(int j=0;j<t;j+=(i<<1)){
            int w=1;
            for(int k=j;k<j+i;++k,w=(long long)w*wn%p){int x=a[k],y=(long long)w*a[k+i]%p;a[k]=p-x>y?x+y:y-(p-x);a[k+i]=x<y?p-(y-x):x-y;}
        }
    }
}
int main(){
	char c=getchar();
    for(;isdigit(c);c=getchar())A[n++]=c^48;
    std::reverse(A,A+n);
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())B[m++]=c^48;
    std::reverse(B,B+m);
    t=n+m+1;l=(t&-t)==t?__builtin_ctz(t):32-__builtin_clz(t);t=1<<l;
    for(int i=1;i<t;++i)rev[i]=(i&1)<<l-1|rev[i>>1]>>1;
    NTT(A,0);NTT(B,0);
    for(int i=0;i<t;++i)A[i]=(long long)A[i]*B[i]%p;
    NTT(A,1);int inv=(long long)(p-1)*(p-1)/t%p;
    for(int i=0;i<t;++i)A[i]=(long long)A[i]*inv%p;
    for(int i=0;i<t;++i)if(A[i]>9)A[i+1]+=A[i]/10,A[i]%=10;
	for(;A[t];++t)if(A[t]>9)A[t+1]=A[t]/10,A[t]%=10;
	for(;t&&!A[t-1];--t);
	for(;t--;)printf("%d",A[t]);
    return 0;
}
2022/5/4 23:12
加载中...