G20 NTT-多项式乘法 • EH's Blog

题目情境#

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

题目描述

给定一个 $n$ 次多项式 $F(x)$ ，和一个 $m$ 次多项式 $G(x)$ 。

请求出 $F(x)$ 和 $G(x)$ 的乘积。

输入格式

第一行两个整数 $n,m$ 。

接下来一行 $n+1$ 个整数，从低到高表示 $F(x)$ 的系数。

接下来一行 $m+1$ 个整数，从低到高表示 $G(x)$ 的系数。

输出格式

一行 $n+m+1$ 个整数，从低到高表示 $F(x) \cdot G(x)$ 的系数。

输入 #1

1 2
1 2
1 2 1

plaintext

输出 #1

1 4 5 2

plaintext

保证输入中的系数均为大于等于 $0$ 且小于等于 $9$ 的整数。

对于 $100\%$ 的数据： $0 \le n, m \leq {10}^6$ 。

算法解析：#

NTT 数论变换：用模素数 $P=998244353$ 的原根 $g=3$ 替代复数单位根做 FFT，避免浮点误差，结果取模。实现与 FFT 相同（位逆序 + 蝶形），逆变换时用 $g$ 的逆元。 $O(n\log n)$ 。

C++代码实现#

// 迭代版 1.5s
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
const int N=4e6;
const int g=3,P=998244353;
int n,m,R[N],gi,ni;
LL A[N],B[N];

LL qpow(LL a,LL b){
  LL ans=1;
  for(;b; a=a*a%P,b>>=1)
    if(b&1) ans=ans*a%P;
  return ans;
}
void NTT(LL A[],int n,int op){
  for(int i=0; i<n; ++i)
    R[i]=R[i/2]/2+((i&1)?n/2:0);      
  for(int i=0; i<n; ++i)
    if(i<R[i]) swap(A[i],A[R[i]]);
  for(int i=2; i<=n; i<<=1){
    LL g1=qpow(op==1?g:gi,(P-1)/i);
    for(int j=0; j<n; j+=i){
      LL gk=1;
      for(int k=j; k<j+i/2; ++k){
        LL x=A[k], y=gk*A[k+i/2]%P;
        A[k]=(x+y)%P;A[k+i/2]=(x-y+P)%P;
        gk=gk*g1%P;
      }
    }
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=0;i<=n;++i)scanf("%lld",A+i);
  for(int i=0;i<=m;++i)scanf("%lld",B+i);
  for(m=n+m,n=1; n<=m; n<<=1);
  gi=qpow(g,P-2); ni=qpow(n,P-2);
  NTT(A,n,1); NTT(B,n,1);
  for(int i=0;i<n;++i)A[i]=A[i]*B[i]%P;
  NTT(A,n,-1);
  for(int i=0;i<=m;++i)
    printf("%d ",A[i]*ni%P);
}