NTT
<p>用于求多项式卷积:</p>
<p><img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/e8a840c19bd52676ce023c6b105cf76f" alt="" /></p>
<pre><code class="language-cpp">#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 100005, mod = 998244353, G = 3;//模数必须为998244353，1004535809，469762049
ll A[maxn], b[maxn];//注意从下标为0开始存值
ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void NTT(ll *a, int n, int opt = 1){
for(int i = 1, j = n >> 1; i < n - 1; i++){
if(i < j) swap(a[i], a[j]);
int k = n >> 1;
for(; j >= k; k >>= 1) j -= k;
if(j < k) j += k;
}
for(int h = 2; h <= n; h <<= 1){
int hh = h >> 1;
int wn = qpow(G, (opt == 1)? (mod - 1) / h: mod - 1 - (mod - 1) / h);
for(int i = 0; i < n; i += h){
ll w = 1;
for(int j = i; j < i + hh; j++){
int x = a[j], y = w * a[j + hh] % mod;
a[j] = (x + y) % mod;
a[j + hh] = (x - y + mod) % mod;
w = w * wn % mod;
}
}
}
if(opt == -1){
int inv = qpow(n, mod - 2);
for(int i = 0; i < n; i++) a[i] = a[i] * inv % mod;
}
}
int main(){
int n; scanf("%d", &n);
//将最长的那个多项式的次数n进行变换得到tn
while(tn < 2 * n + 1) tn <<= 1;
NTT(A, tn), NTT(B, tn);
for(int i = 0; i < tn; i++) A[i] = A[i] * B[i] % mod;
NTT(A, tn, -1);
return 0;
}</code></pre>