题目描述

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

过程

设多项式有 $n$ 项,$n$ 为 $2$ 的整数次幂，不足用 $0$ 补足。

若现在已经求出了 $A * B’ \equiv 1 \pmod{x^{\frac{z}{2}}}$，要求的是多项式 $B$ 满足 $A * B \equiv 1 \pmod{x^z}$。

那么

$$B - B’ \equiv 0 \pmod{x^{\frac{z}{2}}}$$

两边平方

$$(B-B’)^2 \equiv 0 \pmod{x^z}$$

$$B^2 - 2BB’ + B’^2 \equiv 0 \pmod{x^z}$$

同时乘以多项式 $A$

$$B - 2B’ + AB’^2 \equiv 0 \pmod{x^z}$$

$$B = 2B’ - AB’^2 \equiv 0 \pmod{x^z}$$

于是就可以用 $B’$ 推出 $B$，然后一步步推就得到了答案。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1000010, M = 25, g = 3, gi = 332748118;
const ll mod = 998244353;

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

int rev[1 << M];
ll a[N], b[N], t[N];

void init(int n) {
    int lgn = (int)log2(n);
    for (int i = 0; i < n; i ++ ) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lgn - 1));
}

void ntt(ll *a, int n, int Inv = 0) {
    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) {
        ll gn = qpow(Inv ? gi : g, (mod - 1) / (i << 1));
        for (int j = 0; j < n; j += (i << 1)) {
            ll gk = 1;
            for (int k = 0; k < i; k ++ , gk = gk * gn % mod) {
                ll x = a[j + k], y = gk * a[i + j + k] % mod;
                a[j + k] = (x + y) % mod, a[i + j + k] = (x - y + mod) % mod;
            }
        }
    } if (Inv) {
        ll inv = qpow(n, mod - 2);
        for (int i = 0; i < n; i ++ ) a[i] = a[i] * inv % mod;
    }
}

void Inv(ll *a, int n) {
    memset(t, 0, sizeof t);
    t[0] = qpow(a[0], mod - 2);
    int k = 1;
    do {
        k <<= 1; init(k << 1);
        for (int i = 0; i < k; i ++ ) b[i] = a[i];
        for (int i = k; i < (k << 1); i ++ ) b[i] = 0;
        ntt(b, k << 1); ntt(t, k << 1);
        for (int i = 0; i < (k << 1); i ++ ) t[i] = (t[i] * 2 - t[i] * t[i] % mod * b[i] % mod + mod) % mod;
        ntt(t, k << 1, 1);
        for (int i = k; i < (k << 1); i ++ ) t[i] = 0;
    } while (k < n);
    for (int i = 0; i < n; i ++ ) a[i] = t[i];
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &a[i]);
    Inv(a, n);
    for (int i = 0; i < n; i ++ ) printf("%lld ", a[i]);
    return 0;
}