「算法笔记」多项式快速幂

求多项式快速幂时,可以转化成自然对数和指数函数计算。


概述

给定一个 $n - 1$ 次多项式 $A(x)$ 和自然数 $k$,你需要求出多项式 $B(x)$ 满足 $B(x) \equiv A ^ k(x) \pmod{x ^ n}$。


思路

显然我们可以把式子化为:

$$ B(x) \equiv \exp(k\cdot \ln A(x)) \pmod{x ^ n} $$

我们考虑如下两个特殊情况:

  • $A(0) > 1$:我们要把 $A(x)$ 除以 $A(0)$ 后在式子最后乘上去。即为:

$$ B(x) \equiv \exp(k\cdot \ln \frac{A(x)}{A(0)}) \cdot A(0) ^ k \pmod{x ^ n} $$

  • $A(0) = 0$:设多项式 $A(x)$ 从常数项起有 $p$ 个项系数为 $0$,我们把多项式右移 $p$ 位(整除 $x ^ p$)后就转化为第一种情况了。最后再把多项式左移 $pk$ 位(乘以 $x ^ {pk}$)就是答案。

时间复杂度:$\mathcal O(n \log n)$。


代码

Vec operator ^ (Vec A, int k) {
    int n = A.size(), x = 0;
    for (; x < n && A[x] == 0; x++);
    if (1LL * x * k >= n) return Vec(n, 0);
    A = A >> x;
    int v = A[0];
    return (exp(ln(A) * k) * pow(v, k)) << (x * k);
}

发表评论