洛谷P1919--A*B Problem升级版（NTT优化高精度乘法）

题目链接：https://www.luogu.com.cn/problem/P1919

题目背景

本题数据已加强，请使用 FFT/NTT，不要再交 Python 代码浪费评测资源。

题目描述

给你两个正整数

输入格式

第一行一个正整数，表示

输出格式

输出一行一个整数表示答案。

输入输出样例

输入

114514 
1919810

输出

219845122340

说明/提示

【数据范围】
$10^{1000000}$$

可能需要一定程度的常数优化。

emmmm，刚开始学FFT/NTT的可能一下子没有反应过来，我们设输入$s$，那么这个数必然能被表示成$s=a_0*10^0+a_1*10^1+a_2*10^2+cdots $。。。然后就是个愉快的卷积了^_^，只不过要稍微注意一下顺序的问题和边界的处理

以下是AC代码：

/*
    实质上就是将一个数变成a_0*10^0+a_1*10+a_2*10^2...然后就可以快乐地卷积了
*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <string>
using namespace std;

#define IOS ios::sync_with_stdio(false);
typedef long long ll;
const int mac=3e6+10;
const int mod=998244353;

ll a[mac],b[mac],rt[5][30];
int r[mac];
string s1,s2;

ll qpow(ll a,ll b)
{
    ll ans=1;
    a%=mod;
    while (b){
        if (b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans%mod;
}

void NTT(int len,ll *a,int type)
{
    for (int i=0; i<len; i++)
        if (i<r[i]) swap(a[i],a[r[i]]);
    int nb=1;
    for (int mid=1; mid<len; mid<<=1){
        //ll wn=qpow(G,(mod-1)/(mid<<1));//原根代替单位根
        //if (type==-1) wn=qpow(wn,mod-2);//逆变换要乘上逆元
        ll wn=rt[type+1][nb++];
        for (int j=0; j<len; j+=(mid<<1)){
            ll w=1;
            for (int k=0; k<mid; k++,w=(w*wn)%mod){
                ll x=a[j+k],y=w*a[j+k+mid]%mod;
                a[j+k]=(x+y)%mod;
                a[j+k+mid]=(x-y+mod)%mod;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    for (int i=0; i<=25; i++){//预处理出每个长度下的逆元
        int len=1<<i;
        rt[2][i]=qpow(3,(mod-1)/len);//正变换
        rt[0][i]=qpow(rt[2][i],mod-2);//逆变换
    }
    IOS;
    cin.tie(0); cout.tie(0);
    cin>>s1>>s2;
    int len1=s1.length(),len2=s2.length();
    for (int i=0; i<len1; i++)
        a[i]=s1[len1-i-1]-'0';
    for (int i=0; i<len2; i++)
        b[i]=s2[len2-i-1]-'0';
    int len=1,l=0;
    while (len<=len1+len2) len<<=1,l++;
    for (int i=0; i<len; i++)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(len,a,1); NTT(len,b,1);
    for (int i=0; i<len; i++)
        a[i]=(a[i]*b[i])%mod;
    NTT(len,a,-1);
    ll inv=qpow(len,mod-2);
    for (int i=0; i<=len1+len2; i++)
        a[i]=a[i]*inv%mod;
    for (int i=0; i<len1+len2; i++){
        if (a[i]>=10) {a[i+1]+=a[i]/10; a[i]%=10;}
    }
    int tail=len1+len2;
    while (a[tail]==0 && tail>0) tail--;
    while (a[tail]>=10) {a[tail+1]+=a[tail]/10; a[tail++]%=10;}
    for (int i=tail; i>=0; i--)
        printf("%d",a[i]);
    printf("
");
    return 0;
}