多项式求逆

描述

给定多项式 ，求 。

解法

倍增法

首先，易知

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

两边平方可得：

两边同乘 并移项可得：

递归计算即可。

时间复杂度

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
build本页面最近更新：2021/8/22 16:34:31，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：abc1763613206, Enter-tainer, fps5283, H-J-Granger, hly1204, Ir1d, ouuan, StudyingFather, TrisolarisHD
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论