【模板】多项式求逆

题目

要求出满足\(F(x)?G(x)≡1 (mod x^n)\)
假设已知\(F(x)*H(x) ≡1 (mod x^\lceil \frac{n}{2} \rceil)\)
又\(F(x)*G(x) ≡1 (mod x^\lceil \frac{n}{2} \rceil)\)
所以\(F(x)*(G(x)-H(x)) ≡ 0 (mod x^\lceil \frac{n}{2} \rceil)\)
两边平方\(G(x)^2+H(x)^2-2G(x)H(x) ≡ 0 (mod x^n)\)
两边同时乘F(x) \(F(x)G(x)^2+H(x)^2F(x)-2F(x)G(x)H(x) ≡ 0 (mod x^n)\)
可得\(G(x) ≡ 2H(x)-H(x)^2*F(x) (mod x^n)\)
然后用NTT做多项式乘法...
因为第一次写这个，而且NTT也不是很熟练，所以是连写带贺的QWQ过段时间再来重构

#include <bits/stdc++.h>
using namespace std;
const int Mo = 998244353;
const int MAXN = 2100000;
int n, a[MAXN], b[MAXN], d[MAXN], rev[MAXN];
inline int read() {
    char ch; bool f = false; int res = 0;
    while (((ch = getchar()) < '0' || ch > '9') && ch != '-');
    if (ch == '-') f = true; else res = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9') res = (res << 3) + (res << 1) + ch - '0';
    return f? ~res + 1 : res;
}
inline int ksm (int x, int y) {
    int sum = 1;
    for (; y; ) {
        if (y & 1)
            sum = 1LL * sum * x % Mo;
            y >>= 1;
            x = 1LL * x * x % Mo; 
    }
    return sum;
}
void NTT (int *a, int n, int x){
    for (int i = 0; i < n; ++ i) 
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1) {
        int y = ksm(3, (Mo - 1) / (i << 1));
        for (int j = 0; j < n; j += (i << 1)) {
            int x1, x2, x3 = 1;
            for (int k = 0; k < i; ++ k, x3 = 1LL * x3 * y % Mo) {
                x1 = a[j + k];
                x2 = 1LL * x3 * a[j + k + i] % Mo;
                a[j + k] = (x1 + x2) % Mo;
                a[j + k + i] = (x1 - x2 + Mo) % Mo;
            }
        }
    }
    if (x == 1) 
        return;
    int z = ksm(n, Mo - 2);
    reverse(a + 1, a + n);
    for (int i = 0; i < n; ++ i)
        a[i] = 1LL * a[i] * z % Mo;
}
void work (int c, int *a, int *b) {
    if (c == 1) {
        b[0] = ksm(a[0], Mo - 2);
        return;
    }
    work((c + 1) >> 1, a, b);
    int len = 0, x = 1;
    while (x < (c << 1))
        x <<= 1, ++ len;
    for (int i = 1; i < x; ++ i) 
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
    for (int i = 0; i < c; ++ i)
        d[i] = a[i];
    for (int i = c; i < x; ++ i)
        d[i] = 0;
    NTT(d, x, 1);
    NTT(b, x, 1);
    for (int i = 0; i < x; ++ i)
        b[i] = 1LL * (2 - 1LL * d[i] * b[i] % Mo + Mo) % Mo * b[i] % Mo;
    NTT(b, x, -1);
    for (int i = c; i < x; ++ i)
        b[i] = 0;   
}
int main() {
    n = read();
    for (int i = 0; i < n; ++ i)
        a[i] = read();
    work(n, a, b);
    for (int i = 0; i < n; ++ i)
        printf("%d ", b[i]);
    return 0;
}

【模板】多项式求逆

原文：https://www.cnblogs.com/wjnclln/p/10576231.html