多项式求逆元

日付: 10月 28, 2018

对多项式$A(x)$，要求一个$B(x)$，满足$A(x)B(x) \equiv 1 \pmod{x^n}, \quad Deg(B) \le Deg(A)$

1. 当$n=1$时，显然$B_0 = A_0^{-1}$
2. 当$n>1$时，可以倍增处理，如果已知$$A(x)B'(x) \equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}}$$显然$$A(x)B(x) \equiv 1 \pmod{x^{\lceil \frac{n}{2}\rceil}}$$联立两式得$$B(x)-B'(x) \equiv 0 \pmod{x^{\lceil \frac{n}{2}\rceil}}$$各部分取平方后得$$B^2(x)-2B(x)B'(x) + B'^2(x) \equiv 0 \pmod{x^n}$$同时乘上$A(x)$，由逆元的定义，得$$B(x) \equiv B'(x)(2-A(x)B'(x)) \pmod{x^n}$$这样就可以根据$B'(x)$推出$B(x)$了，因为是倍增的，且每一步多项式乘法可以用FFT加速，总时间复杂度是$O(nlog(n))$

## Code
假设已经有能处理所需模数的FFT/NTT，并且实现了`multiply`方法。(如果直接调用`fourier_transform`可以优化常数。)
```c++
int mpow(long long a, int k, int m) { int r(1); for (a %= m; k; k >>= 1, a = a * a % m) if (k & 1)r = r * a % m; return r; }
template <typename T> vector<T> inv(const vector<T> &A, int n, int p) {
    assert(is_integral<T>::value && A[0]);
    vector<T> R;
    function<void(int)> inv_ = [&](int n) {
        if (n == 1) return R = {mpow(A[0], p - 2, p)}, void();
        inv_((n + 1) >> 1);
        auto Tmp = multiply(A, R, p);
        Tmp[0] = (2 - Tmp[0] + p) % p;
        for (size_t i = 1; i < Tmp.size(); i++) Tmp[i] = Tmp[i] ? p - Tmp[i] : 0;
        R = multiply(R, Tmp, p);
        R.resize(n);
    };
    inv_(n);
    return R;
}
```
## Related
[FFT与NTT](https://kongroo.blogspot.com/2018/10/fftntt.html)

KONGROOの基地

このブログを検索

多项式求逆元

コメント

コメントを投稿