多项式全家桶

First Post:

Last Update:

Word Count:
1.6k

Read Time:
7 min

Page View: loading...

多项式乘法

首先，我们应该对多项式乘法给出定义，给定多项式 和 ：

定义它们的乘积 为：

Algo 1

因此，我们容易想到 暴力模拟。

1
2
3
for (int i = 0; i <= n; ++i)
  for (int j = 0; j <= n; ++j)
    c[i + j] += a[i] * b[j];

时间复杂度 （假定 ）。

Algo 2

在模数难以 NTT 并不想打 MTT 等毒瘤算法时使用。

考虑分治，首先，将 和 都补齐到 项。

任取 ，记

这里， 为次数小于 的多项式。

容易得到：

这需要 次多项式乘法，考虑使用加法替代一次。

注意到：

因此，我们可以将原问题化为 个规模更小的子问题。

取 ，记计算多项式乘法的耗时为 ，则

由主定理，。

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
27
28
29
30
template <typename Int> Int *karatsuba_polymul(Int *a, Int *b, size_t n) {
  if (n <= 32) {
    Int *r = new Int[n << 1 | 1]();
    for (size_t i = 0; i <= n; ++i)
      for (size_t j = 0; j <= n; ++j)
        r[i + j] += a[i] * b[j];
    return r;
  }
  size_t m = (n >> 1) + 1;
  Int *z0, *z1, *z2;
  z0 = karatsuba_polymul(a, b, m - 1);
  z2 = karatsuba_polymul(a + m, b + m, n - m);

  for (size_t i = 0; i + m <= n; ++i) a[i] += a[i + m];
  for (size_t i = 0; i + m <= n; ++i) b[i] += b[i + m];
  z1 = karatsuba_polymul(a, b, m - 1);
  for (size_t i = 0; i + m <= n; ++i) a[i] -= a[i + m];
  for (size_t i = 0; i + m <= n; ++i) b[i] -= b[i + m];

  for (size_t i = 0; i <= (m - 1) << 1; ++i) z1[i] -= z0[i];
  for (size_t i = 0; i <= (n - m) << 1; ++i) z1[i] -= z2[i];

  Int *r = new Int[m << 2 | 1]();
  for (size_t i = 0; i <= (m - 1) << 1; ++i) r[i] += z0[i];
  for (size_t i = 0; i <= (m - 1) << 1; ++i) r[i + m] += z1[i];
  for (size_t i = 0; i <= (n - m) << 1; ++i) r[i + (m << 1)] += z2[i];

  delete[] z0, z1, z2;
  return r;
}

这种算法叫 Karatsuba 乘法。

Algo 3

我们知道，除了多项式的系数表达法， 个点值（一般）也可以唯一确定一个 项多项式。而点值表示的多项式可以在 的时间复杂度内相乘。

因此考虑选择 个点使得可以快速求出它们的点值。

由于其良好的性质，我们选择 次单位根，同时称这个过程为 FFT。

先将给定多项式补齐到 项，例如：

考虑分治，将奇数项和偶数项分开。

定义 和 是 项的多项式：

则

考虑 在 处的点值：

同理有：

因此，只需计算 和 在 次单位根上的点值，就能计算出 在 次单位根上的点值；因此递归对 和 做 FFT 即可。

容易看出，算法的时间复杂度满足 ，因此 FFT 的时间复杂度为 。

IFFT

得到多项式的点值后，我们考虑如何将点值形式转化为系数形式。

FFT 可以看作系数向量乘变换矩阵：

因此，IFFT 计算变换矩阵的逆矩阵。

观察到变换矩阵的逆矩阵为：

换句话说，IFFT 变换矩阵是将 FFT 变换矩阵的各项取倒数再除以 。

因此只需在 FFT 的算法的基础上修改少量代码。

位逆序置换

朴素的 FFT 递归地将多项式奇偶项系数分开，这个过程需要大量的数组复制，递归进行也将产生更多的时空间开销。

考虑在最开始模拟递归分割数组的结果，然后使用倍增法合并区间。

注意到，新下标为原下标在二进制下的反转（0-index）。

例如：

因此，我们可以使用递推的方法 计算出每个数反转后的结果并交换：

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
27
28
29
30
31
using Complex = complex<double>;

template <typename T> constexpr void change(vector<T> &a) {
  size_t n = a.size();
  vector<size_t> rev(n);
  for (size_t i = 0; i < n; ++i) {
    rev[i] = rev[i >> 1] >> 1;
    if (i & 1)
      rev[i] |= n >> 1;
    if (i < rev[i])
      swap(a[i], a[rev[i]]);
  }
}

template <int32_t on = 1> constexpr void fft(vector<Complex> y) {
  static_assert(on == 1 || on == -1, "on must be 1 or -1");
  change(y);
  for (size_t h = 2; h <= y.size(); h <<= 1) {
    Complex wn(cos(2 * M_PI / h), sin(on * 2 * M_PI / h));
    for (size_t j = 0; j < y.size(); j += h) {
      Complex w(1, 0);
      for (size_t k = j; k < j + (h >> 1); ++k, w *= wn) {
        Complex u = y[k], t = w * y[k + (h >> 1)];
        y[k] = u + t, y[k + (h >> 1)] = u - t;
      }
    }
  }
  if constexpr (on == -1)
    for (int i = 0; i < len; ++i)
      y[i] /= len;
}

Algo 4

题目中为了避免精度问题，常常让我们对大质数取模。

这时，我们可以使用 NTT 替代 FFT。

其实，NTT 就是模意义下的 FFT。

根据原根的定义和存在性定理，对于奇质数 ，其原根 就是它的 次单位根；因此，模 意义下存在 次单位根当且仅当 可以整除 。

由于 FFT 中使用的是 次单位根，我们需要的是 形式的质数，这里 需要足够大。

常见的模数有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <uint64_t p, uint64_t g, bool inv = false>
constexpr void ntt(vector<uint64_t> &a) {
  change(a);
  const int64_t n = a.size();
  constexpr uint64_t gg = inv ? fast_pow<p>(g, p - 2) : g;
  for (uint64_t h = 2; h <= n; h <<= 1) {
    uint64_t wn = fast_pow<p>(gg, (p - 1) / h);
    for (uint64_t i = 0; i < n; i += h) {
      for (uint64_t j = i, w = 1; j < i + (h >> 1); ++j, w = w * wn % p) {
        uint64_t u = a[j], v = a[j + (h >> 1)] * w % p;
        a[j] = (u + v) % p, a[j + (h >> 1)] = (u + p - v) % p;
      }
    }
  }
  if constexpr (inv) {
    const int64_t inv_n = fast_pow<p>(n, p - 2);
    for (uint64_t &x : a)
      x = x * inv_n % p;
  }
}

多项式初等函数

如无说明，以下内容中的多项式很可能是在模 意义下讨论的（截断到 项）。

多项式对数函数

首先，根据多项式复合的定义，若 存在，则 。

考虑将 求导后积分：

多项式三角/反三角函数

感觉没啥应用？

三角函数直接套用欧拉公式：

反三角函数仍然求导后积分：

将式中的 替换为 即可。

多项式牛顿迭代法

给定二元函数 ，已知多项式 满足

并且存在 满足：

  • ；
  • 。

求 在模 意义下的结果。

考虑倍增构造：

首先， 时，单独求出 的解，假设中的 为一个解。

如果已经得到了模 意义下的解 ，尝试构造模 意义下的解。

将 在 处泰勒展开，由题意：

由于 的最低非零项次数为 ，因此：

代入泰勒展开式：

因此

多项式求逆

设给定函数为 。

利用牛顿迭代法，令

则

多项式开方

设给定函数为 ，有

则

多项式指数函数

设给定函数为 ，有

则

≡