多项式求逆

描述

给定多项式 ,求

解法

倍增法

首先,易知

假设现在已经求出了 在模 意义下的逆元 。 有:

两边平方可得:

两边同乘 并移项可得:

递归计算即可。

时间复杂度

Newton's Method

参见 Newton's Method.

Graeffe 法

欲求 考虑

只需求出 即可还原出 因为 是偶函数,时间复杂度同上。

代码

多项式求逆
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
constexpr int maxn = 262144;
constexpr int mod = 998244353;

using i64 = long long;
using poly_t = int[maxn];
using poly = int *const;

void polyinv(const poly &h, const int n, poly &f) {
  /* f = 1 / h = f_0 (2 - f_0 h) */
  static poly_t inv_t;
  std::fill(f, f + n + n, 0);
  f[0] = fpow(h[0], mod - 2);
  for (int t = 2; t <= n; t <<= 1) {
    const int t2 = t << 1;
    std::copy(h, h + t, inv_t);
    std::fill(inv_t + t, inv_t + t2, 0);

    DFT(f, t2);
    DFT(inv_t, t2);
    for (int i = 0; i != t2; ++i)
      f[i] = (i64)f[i] * sub(2, (i64)f[i] * inv_t[i] % mod) % mod;
    IDFT(f, t2);

    std::fill(f + t, f + t2, 0);
  }
}

例题

  1. 有标号简单无向连通图计数:「POJ 1737」Connected Graph