洛谷P4238 【模板】多项式乘法逆 题解

题目链接：P4238 【模板】多项式乘法逆

题意：

给定一个多项式 \(F(x)\) ，请求出一个多项式 \(G(x)\)， 满足 \(F(x) \cdot G(x) \equiv 1 \pmod{x^n}\)。系数对 \(998244353\) 取模。

输入格式：

首先输入一个整数 \(n\)， 表示输入多项式的项数。
接着输入 \(n\) 个整数，第 \(i\) 个整数 \(a_i\) 代表 \(F(x)\) 次数为 \(i-1\) 的项的系数。

输出格式：

输出 \(n\) 个数字，第 \(i\) 个整数 \(b_i\) 代表 \(G(x)\) 次数为 \(i-1\) 的项的系数。保证有解。

数据范围：

对于 \(100\%\) 的数据，\(1 \leq n \leq 10^5\)，$ 0 a_i ^9$。

首先，易知 \[ [x^0]f^{-1}(x) = ([x^0]f(x))^{-1} \] 假设现在已经求出了 \(f(x)\) 在模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) 下的逆元 \(f_0^{-1}(x)\) ，有 \[ \begin{aligned} f(x) f_0^{-1}(x) & \equiv 1 &\pmod{ x^{\left\lceil\frac{n}{2}\right\rceil}} \\[6pt]f(x) f^{-1}(x) & \equiv 1 & \pmod{ x^{\left\lceil\frac{n}{2}\right\rceil}} \\[6pt]f^{-1}(x)-f_0^{-1}(x) & \equiv 0 &\pmod{ x^{\left\lceil\frac{n}{2}\right\rceil}} \end{aligned} \] 两边平方可得 \[ f^{-2}(x)-2 f^{-1}(x) f_0^{-1}(x)+f_0^{-2}(x) \equiv 0 \pmod{ x^n} \] 两边同乘 \(f(x)\) 并移项可得 \[ f^{-1}(x) \equiv f_0^{-1}(x)\left(2-f(x) f_0^{-1}(x)\right)\pmod{ x^n } \] 递归处理即可。

时间复杂度 \(T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(n \log n) = \mathcal{O}(n \log n)\)​​ 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2097152 + 15))

const int P = 998244353;
const int G = 3, Gi = 332748118;
int a[N], b[N], c[N], r[N];
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % P;
        b >>= 1; a = a * a % P;
    }
    return r;
}
void NTT(int *A, int limit, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            int w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P)
            {
                int x = A[j + k], y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
    if(type == -1)
    {
        int Inv = qpow(limit, P - 2);
        for(int i = 0; i < limit; i++) A[i] = A[i] * Inv % P;
    }
}
void solve(int n, int *a, int *b)
{
    if(n == 1) { b[0] = qpow(a[0], P - 2); return; }
    solve((n + 1) / 2, a, b);
    int l = 0, limit = 1;
    for(; limit <= (n - 1) * 2; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    for(int i = 0; i < n; i++) c[i] = a[i];
    for(int i = n; i < limit; i++) c[i] = 0;
    NTT(c, limit, 1); NTT(b, limit, 1);
    for(int i = 0; i < limit; i++)
        b[i] = (2 - c[i] * b[i] % P + P) % P * b[i] % P;
    NTT(b, limit, -1);
    for(int i = n; i < limit; i++) b[i] = 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 0, x; i < n; i++) cin >> x, a[i] = (x + P) % P;
    solve(n, a, b);
    for(int i = 0; i < n; i++) cout << b[i] << " \n"[i == n - 1];
    return 0;
}

---

传送门：多项式初等函数 。