多项式乘法逆

给你多项式 ，寻找一个多项式满足 。考虑倍增求解。 如果我们已知 ，而根据 。那么显然 ,两式相减那么 ,左右相减 。考虑左右都乘上一个 ，那么 移项 。那我们的递归出口为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p = 998244353,Gi = 3,N = 2e6+100;
#define LL long long
int read() {int x;scanf("%lld",&x);return x;}
int qpow(int a,int b) {
    int x = 1;for(;b;b >>= 1,a = 1LL * a * a % p) {
        if(b&1) x = 1LL * x * a % p;
    }
    return x;
}
int f[N],g[N],g2[N],r[N];
void ntt(int *a,int type,int limit) {
    for(int i = 0;i < limit;i++) if(i < r[i]) swap(a[i],a[r[i]]);
    for(int mid = 1;mid < limit;mid <<= 1) {
        int wn = qpow(Gi,(p-1)/(mid<<1));
        for(int i = 0;i < limit;i+=(mid<<1)) {
            int w = 1;
            for(int j = 0;j < mid;j++,w = 1LL * w * wn % p) {
                int x = a[i + j],y = 1LL * w * a[i + j + mid] % p;
                a[i + j] = (x + y) % p;
                a[i + j + mid] = (x - y + p) % p;
            }
        }
    }
    if(type == -1) {
        int inv = qpow(limit,p-2);
        if(limit > 1) reverse(a+1,a+limit);
        for(int i = 0;i < limit;i++) a[i] = 1LL * a[i] * inv % p;
    }
}
void Inv(int *a,int *b,int deg) {
    if(deg == 1) {b[0] = qpow(a[0],p-2);return;}
    Inv(a,b,(deg+1)>>1);
    int L = 0,limit = 1;
    while(limit <= deg + deg - 2) limit <<= 1,L++;
    for(int i = 0;i < limit;i++) r[i] = (r[i>>1]>>1)|((i&1)<<L-1);
    for(int i = 0;i < deg;i++) g2[i] = a[i];
    for(int i = deg;i < limit;i++) g2[i] = 0;
    ntt(g2,1,limit);ntt(b,1,limit);
    for(int i = 0;i < limit;i++) {
        b[i] = ((2LL - b[i] * g2[i] % p) + p) % p * b[i] % p;
    }
    ntt(b,-1,limit);
    for(int i = deg;i < limit;i++) b[i] = 0;
}
signed main() {
    int n = read() - 1;
    for(int i = 0;i <= n;i++) f[i] = read();
    Inv(f,g,n+1);
    for(int i = 0;i <= n;i++) printf("%lld ",g[i]);
    printf("\n");return 0;
}