【模板】多項式乘法（FFT）

題目背景

這是一道多項式乘法模板題。

注意：本題并不屬于中國計算機學會劃定的提高組知識點考察范圍。

題目描述

給定一個 $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)?G(x)$ 的系數。

樣例 #1

樣例輸入 #1

1 2
1 2
1 2 1

樣例輸出 #1

1 4 5 2

提示

保證輸入中的系數大于等于 $0$ 且小于等于 $9$。

對于 $100\%$ 的數據：$1\le n,m\le {10}^6$。

原題

洛谷P3803——傳送門

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;// NTT的特殊要求:模數P需滿足P=k*2^m+1，例如常用的模數998244353=7*17*2^23+1
const int Mod = 998244353;
const int G = 3; // 998244353的原根為3
const int maxn = 1e6 + 6;int QuickPow(int a, int k) // 快速冪
{int ret = 1;while (k){if (k & 1)ret = 1LL * ret * a % Mod;a = 1LL * a * a % Mod;k >>= 1;}return ret;
}int rev[3 * maxn];
inline void GetReverse(int len, int lg) // 獲得二進制位的反轉
{for (int i = 0; i < len; i++)rev[i] = 0;for (int i = 0; i < len; i++)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
}void NTT(vector<int> &a, int dir)
{int len = a.size();for (int i = 0; i < len; i++)if (i < rev[i])swap(a[i], a[rev[i]]);int g = (dir == 1 ? G : QuickPow(G, Mod - 2));for (int stp = 1; stp < len; stp <<= 1){int wn = QuickPow(g, (Mod - 1) / (stp << 1));int w = 1;for (int k = 0; k < stp; k++){for (int even = k; even < len; even += stp << 1){int odd = even + stp;int tmp = 1LL * w * a[odd] % Mod;a[odd] = (a[even] - tmp + Mod) % Mod;a[even] = (ll)(a[even] + tmp) % Mod;}w = 1LL * w * wn % Mod;}}if (dir == -1){int inv = QuickPow(len, Mod - 2); // 乘法逆元for (int i = 0; i < len; i++)a[i] = 1LL * a[i] * inv % Mod;}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 以下代碼實現了多項式f(x)和多項式g(x)相乘int n, m;cin >> n >> m;int lg = 0;int bound = 1; // 將多項式的系數擴充到2的整數次冪while (bound <= n + m){bound <<= 1;lg++;}GetReverse(bound, lg);vector<int> f(bound, 0), g(bound, 0); // 數組大小開到bound(即結果多項式擴充后的大小)for (int i = 0; i <= n; i++){cin >> f[i];}for (int i = 0; i <= m; i++){cin >> g[i];}NTT(f, 1);NTT(g, 1);for (int i = 0; i < bound; i++){f[i] = (1LL * f[i] * g[i]) % Mod; // 將相乘結果存儲在f[]數組中}NTT(f, -1);for (int i = 0; i <= n + m; i++){cout << f[i] << ' ';}return 0;
}