概述

给定一个 $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);
}