NTT

用于求多项式卷积:

#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;
}