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

· · 题解

算法介绍

设 A 是我们要求乘法逆的多项式。

我们需要求 B 满足 A \times B \equiv 1 \pmod{x^n}（注意系数是模 998244353 的）。

假如 C 是满足 A \times C \equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}} 的 \lceil\frac{n}{2}\rceil 次多项式，那么 B \equiv C \times (2 - A \times C) \pmod{x^n}。

所以就可以递归求了。

时间复杂度：

假如 f(n) 是这个算法 n 次多项式的时间复杂度，M(n) 是乘法的时间复杂度。

## 证明 证明如下： 假如 $C$ 是满足 $A \times C \equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}}$ 的 $\lceil\frac{n}{2}\rceil$ 次多项式，则 $A \times B - A \times C \equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}$，因为 $A$ 有乘法逆，所以 $A$ 不是 $x$ 的倍数，所以就可以放心的把 $A$ 除掉，得到 $B - C \equiv 0 \pmod{x^{\lceil\frac{n}{2}\rceil}}$。 我们可以想到要搞出 $\pmod{x^n}$ 可以把式子平方，所以可以得到：$B^2 - 2 \times B \times C + C^2 \equiv 0 \pmod{x^n}$。 已知 $A \times B \equiv 1 \pmod{x^n}$，所以可以两边乘以 $A$，然后得到 $B - 2 \times C + C^2 \times A \equiv 0 \pmod{x^n}$，然后整理合并同类项得到 $B \equiv 2 \times C - C^2 \times A \equiv C \times (2 - A \times C) \pmod{x^n}

然只要实现多项式乘法就行了。模 998244353 正好能用快速数论变换。

代码

int mod_inv(int n){
    return qpow(n, MOD - 2);
}
void memset_(int *a, int x, int y){
    for(int i = x;i <= y;i++)a[i] = 0;
}
void inv(int n, int *a, int *b){
    if(n == 1){
        b[0] = mod_inv(a[0]);
        return;
    }
    int m = (n + 1) / 2;
    inv(m, a, b); // b = inv(a) (mod x^(n/2))
    int len = 1;
    while(len < n * 2)len <<= 1;
    for(int i = 0;i < n;i++)c[i] = a[i];
    memset_(c, n, len - 1);
    memset_(b, m, len - 1);
    ntt(c, len, 0);
    ntt(b, len, 0);
    for(int i = 0;i < len;i++){
        ll t = 1ll * c[i] * b[i] % MOD;
        t = (2 - t + MOD) % MOD;
        b[i] = (t * b[i] % MOD); // b = b(2-bc)
    }
    ntt(b, len, 1);
    memset_(b, n, len - 1);
}