NTT多项式乘法模板（HUD 1402）

ゝ一纸荒年。 2022-05-15 12:45 223阅读 0赞

## FFT虽然能快速处理卷积，但是它也有很大的弊端。精度问题有时会导致一些错误。而且，有许多题目涉及了取模，比如 998244353，复数域下的 DFT精度更是暴露无遗。于是考虑是否有模意义下的这种算法。于是，便出现了**快速数论变换**（Fast Number−Theoretic Transform, FNT）。 ##

## NTT和FFT基本上一样，只不过用原根代替了复数根。 ##

## 参考博客：[https://www.cnblogs.com/zhouzhendong/p/8831887.html][https_www.cnblogs.com_zhouzhendong_p_8831887.html] ##

## NTT大数乘法代码： ##

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    typedef pair<int,int> PII;
    const ll mod = 998244353;
    const int N = 1e6+10;
    
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    int to[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}};
    
    ll A,B,a[N],b[N],R[N],g[N],n,L;
    char s1[N],s2[N];
    
    void NTT(ll a[N],int n){
        for (int i=0;i<n;i++) if (i<R[i]) swap(a[i],a[R[i]]);
        for (int d=1,t=n>>1;d<n;d<<=1,t>>=1)
            for (int i=0;i<n;i+=(d<<1))
                for (int j=0;j<d;j++){
                    ll tmp=g[t*j]*a[i+j+d]%mod;
                    a[i+j+d]=(a[i+j]-tmp+mod)%mod;
                    a[i+j]=(a[i+j]+tmp)%mod;
                }
    }
    
    int main() {
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        while(cin>>s1>>s2) {
            mst(a,0),mst(b,0);
            A=strlen(s1),B=strlen(s2);
            for (int i=0;i<A;i++) a[A-i-1]=s1[i]-'0';
            for (int i=0;i<B;i++) b[B-i-1]=s2[i]-'0';
            for (n=1,L=0;n<A+B;n<<=1,L++);
            for (int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
            g[0]=1,g[1]=qp(3,(mod-1)/n);
            for (int i=2;i<n;i++) g[i]=g[i-1]*g[1]%mod;
            NTT(a,n),NTT(b,n);
            for (int i=0;i<n;i++) a[i]=a[i]*b[i]%mod;
            g[0]=1,g[1]=qp(g[1],mod-2);
            for (int i=2;i<n;i++) g[i]=g[i-1]*g[1]%mod;
            NTT(a,n);
            ll Inv=qp(n,mod-2);
            for (int i=0;i<n;i++) a[i]=a[i]*Inv%mod;
            for (int i=0;i<n-1;i++) a[i+1]+=a[i]/10,a[i]%=10;
            int d;
            for (d=n-1;d&&!a[d];d--);
            for (int i=d;i>=0;i--) cout<<a[i];
            cout<<endl;
        }
        return 0;
    }

[https_www.cnblogs.com_zhouzhendong_p_8831887.html]: https://www.cnblogs.com/zhouzhendong/p/8831887.html