多项式幂函数
模板题：Luogu P5245、Luogu P5273。
给定一个 $n-1$ 次多项式 $A(x)$，求一个在 $\bmod\ x^n$ 意义下的多项式 $B(x)$，使得 $B(x) \equiv (A(x))^k \ (\bmod\ x^n)$。多项式的系数在 $\bmod {998244353}$ 的意义下进行运算。
特殊情况：$A_0=1$
即 Luogu P5245。
算法 1：倍增法
$$(A(x))^k \equiv (A(x))^{k \bmod 998244353} \pmod {998244353}$$
直接用类似于整数快速幂的思想做即可，时间复杂度为 $O(n \log n \log (k \bmod 998244353))$。
算法 2
由于$a^b=e^{b\ln a}$，所以可以先求 $k \ln A(x)$，然后再 $\exp$ 回来。这样就可以取模了。
多项式求逆 + 多项式指数函数 + 多项式对数函数，时间复杂度 $O(n\log n)$。
普通版
高度封装版
一般情况
即 Luogu P5273。
算法 1：倍增法
略
算法 2
算法大体同上，只需注意：
- 判断 $A(x)$ 开头的零；
- 若 $A(x)$ 从头开始数的第一个数不为 $1$，需要将每一个数都乘上它的逆元，并在最后做一些处理。
普通版
高度封装版
短多项式幂
题目描述
给定 $d$ 阶多项式 $F(x)$，$d$ 的大小几乎为常数。
求 $F^k(x) \bmod x^{n+1}$。
系数对大质数取模。
简要思路
设 $F(x)=F^k(x)$，两边求导得到：
$$G'(x)=kF^{k-1}(x)F'(x)$$
$$G'(x)F(x)=kF^k(x)F'(x)$$
$$G'(x)F(x)=kF'(x)G(x)$$
$$\sum\limits_{i=0}^d[x^{n-i}]G'(x)[x^i]F(x)=k\sum\limits_{i=0}^{d-1}[x^i]F'(x)[x^{n-i}]G(x)$$
$$\sum\limits_{i=0}^d(n-i+1)[x^{n-i+1}]G(x)[x^i]F(x)=k\sum\limits_{i=0}^{d-1}[x^i]F'(x)[x^{n-i}]G(x)$$
注意到左边出现了 $[x^{n+1}]G(x)$，带入这个式子，即可递推 $G(x)$ 的每一项。