多项式求逆

标签：求逆 frac pmod 多项式 int n2 equiv

类似于逆原，多项式也可以求逆，具体地，定义多项式 \(f(x)\) 的乘法逆为能使得 \(f(x) * g(x) \equiv 1 \pmod{x^n}\) 的多项式 \(g(x)\)，也可记作 \(f(x)^{-1}\)。

假设我们现在已经求出了 \(f(x)\) 在模 \(x^{\lceil\frac n2\rceil}\) 意义下的逆原 \(f_0(x)^{-1}\)。有：

\[\left.\begin{aligned} f(x)f_0(x)^{-1} \equiv 1 \pmod{x^{\lceil\frac n2\rceil}} \\ f(x)f(x)^{-1} \equiv 1 \pmod{x^{\lceil\frac n2\rceil}} \end{aligned}\right\} \Rightarrow f(x)^{-1} - f_0(x)^{-1} \equiv 0 \pmod{x^{\lceil\frac n2\rceil}} \]

两边平方，得：

\[f(x)^{-2} - 2f^{-1}(x)f_0(x)^{-1} + f_0(x)^{-2} \equiv 0 \pmod{x^n} \]

两边同乘 \(f(x)\)，得：

\[f(x)^{-1} \equiv f_0(x)^{-1}[2 - f(x)f_0(x)^{-1}] \pmod{x^n} \]

递归下去就好了，时间复杂度 \(T(n) = T(\dfrac n2) + \mathcal O(n \log n) = \mathcal O(n \log n)\)。

特别地，\(f(x)^{-1} \equiv f(0)^{-1} \pmod x\)。

P4238 【模板】多项式乘法逆

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

constexpr int N = 1 << 18, MOD = 998244353;

int n, f[N], g[N], fg[N];
int len, bits, rev[N];

ll qp(ll base, int e) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    return res;
}

void NTT(int *A, bool I = 0) {
    for (int i = 0; i < len; i++) if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int i = 1; i < len; i <<= 1) {
        ll wn = qp(I ? 332748118 : 3, (MOD - 1) / (i << 1));
        for (int j = 0; j < len; j += (i << 1)) {
            ll w = 1;
            for (int k = j; k < j + i; k++) {
                int t = w * A[k + i] % MOD;
                A[k + i] = (A[k] - t + MOD) % MOD, A[k] = (A[k] + t) % MOD;
                w = w * wn % MOD;
            }
        }
    }
    if (I) {
        ll invlen = qp(len, MOD - 2);
        for (int i = 0; i < len; i++) A[i] = A[i] * invlen % MOD;
    }
}

void solve(int e) {
    if (e == 1) return;
    solve((e + 1) >> 1);
    bits = -1, len = 1; while (len < (e << 1) - 1) len <<= 1, bits++;
    for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bits);
    memcpy(fg, f, e << 2), fill(fg + e, fg + len, 0); NTT(fg), NTT(g);
    for (int i = 0; i < len; i++) fg[i] = (ll)fg[i] * g[i] % MOD;
    for (int i = 0; i < len; i++) g[i] = (ll)g[i] * (2 - fg[i] + MOD) % MOD;
    NTT(g, 1); fill(g + e, g + len, 0);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n; for (int i = 0; i < n; i++) cin >> f[i];
    g[0] = qp(f[0], MOD - 2); solve(n);
    for (int i = 0; i < n; i++) cout << g[i] << ' ';
    return 0;
}

标签：求逆,frac,pmod,多项式,int,n2,equiv
From： https://www.cnblogs.com/chy12321/p/18010730