多项式牛顿迭代
对于\(G(f(x)) = 0\)，求解 \(f\pmod {x^n}\)
$x^{\left\lceil\frac{n}{2}\right\rceil} $ 意义下的解 \(f_{0}\left(x\right)\)，要求模 \(x^{n}\) 意义下的解 \(f\left(x\right)\)。
有结论：
\[f\left(x\right)\equiv f_{0}\left(x\right)-\frac{G\left(f_{0}\left(x\right)\right)}{G'\left(f_{0}\left(x\right)\right)}\pmod{x^{n}} \]考虑倍增，\(G(f(x))\)在\(f_0(x)\)处的泰勒展开即可。
\[\sum_{i=0}^{+\infty}\frac{G^{\left(i\right)}\left(f_{0}\left(x\right)\right)}{i!}\left(f\left(x\right)-f_{0}\left(x\right)\right)^{i}\equiv G(f(x)) \equiv 0\pmod{x^{n}} \]观察到 \(i \ge 2\) 时，式子值为 \(0\)，考虑前两项即可。
多项式求逆
已知\(f(x)\)，\(f(x) * G(x) = 1\)，求\(G(x)\)。
设关于\(G(x)\)的函数\(F(G(x)) = \frac{1}{G(x)} - f(x) = 0\)，设\(G_0(x)\)为\(f(x)\)在\(\mod x^{\lceil\frac{n}{2}\rceil}\)的逆。
所以有
迭代求解即可，时间复杂度为\(O(n\log n)\)。
多项式 \(\text{ln}\)
定义
\[ln(x) = -\sum_{i \ge 1} \frac{(1 - x)^i}{i} \]当然能用定义来求解，这样时间复杂度会爆。
设\(G(x) = \ln x\)，那么\(G'(f(x)) = \frac{f'(x)}{f(x)}\)，多项式求逆即可，时间复杂度\(O(n\log n)\)
多项式 \(\text{exp}\)
定义
\[e^x = \sum_{i\ge0}\frac{x^i}{i!} \]设\(G(x) = e^{f(x)}\)，已知\(f(x)\)，求解\(G(x)\)。
设关于\(G(x)\)的函数\(F(G(x)) = \ln G(x) - f(x) = 0\)。
根据牛顿迭代
迭代求解，时间复杂度\(O(n\log n)\)。
板子
Code
#include<cstdio>
#include<iostream>
#define IN inline
#define LL long long
using namespace std;
const int N = 2e5 + 5, P = 998244353, G = 3;
int n, m, a[N << 2], b[N << 2];
IN int read() {
int t = 0,res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) t |= (ch == '-');
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return t ? -res : res;
}
LL fpow(LL x, LL y) {
LL res = 1;
for (; x; x >>= 1, y = y * y % P)
if (x & 1) res = res * y % P;
return res;
}
const int invG = fpow(P - 2, G);
namespace Poly{
int rev[N << 2], insF[N << 2], sginv[N << 2];
void NTT(int *f, int len, int fl) {
static int W[N << 2] = {1};
if (len == 1) return;
for (int i = 0; i < len; i++)
if (i < rev[i]) swap(f[i], f[rev[i]]);
for (int l = 1; l < len; l <<= 1) {
int I = fpow((P - 1) / (l << 1), fl == 1 ? G : invG);
for (int i = 1; i < l; i++) W[i] = (LL)W[i - 1] * I % P;
for (int i = 0; i < len; i += (l << 1))
for (int j = 0; j < l; j++) {
int x = f[i | j], y = (LL)f[i | j | l] * W[j] % P;
f[i | j] = (x + y >= P ? x + y - P : x + y);
f[i | j | l] = (x - y < 0 ? x - y + P : x - y);
}
}
if (fl == -1) {
int IV = fpow(P - 2, len);
for (int i = 0; i < len; i++) f[i] = (LL)f[i] * IV % P;
}
}
void Mulpoly(int *f, int *g, int lenF, int lenG) {
int len = 1, bit = 0;
while (len <= lenF + lenG) len <<= 1, bit++;
for (int i = 1; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit - 1);
for (int i = lenF + 1; i < len; i++) f[i] = 0;
for (int i = lenG + 1; i < len; i++) g[i] = 0;
NTT(f, len, 1), NTT(g, len, 1);
for (int i = 0; i < len; i++) f[i] = (LL)f[i] * g[i] % P;
NTT(f, len, -1);
for (int i = lenF + lenG + 1; i < len; i++) f[i] = 0;
}
void Invpoly(int *f, int lenF, int *g) { // [0, lenF);
static int s2[N << 2], s1[N << 2];
int limit = 1; while (limit < lenF) limit <<= 1;
g[0] = fpow(P - 2, f[0]);
for (int len = 2, bit = 1; len <= limit; len <<= 1, bit++) {
for (int i = 1; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit - 1);
for (int i = 0; i < (len >> 1); i++) s2[i] = g[i];
for (int i = (len >> 1); i < len; i++) s2[i] = 0;
for (int i = 0; i < len; i++) s1[i] = f[i];
NTT(s2, len, 1), NTT(s1, len, 1);
for (int i = 0; i < len; i++) s1[i] = (LL)s2[i] * s1[i] % P;
NTT(s1, len, -1);
for (int i = 0; i < (len >> 1); i++) s1[i] = 0;
NTT(s1, len, 1);
for (int i = 0; i < len; i++) s1[i] = (LL)s1[i] * s2[i] % P;
NTT(s1, len, -1);
for (int i = (len >> 1); i < len; i++) g[i] = (s1[i] == 0 ? 0 : P - s1[i]);
}
for (int i = lenF; i < limit; i++) g[i] = 0;
for (int i = 0; i < limit; i++) s2[i] = s1[i] = 0;
}
void Getsginv(int len) {
sginv[0] = sginv[1] = 1;
for (int i = 2; i <= len; i++) sginv[i] = (LL)sginv[P % i] * (P - P / i) % P;
}
void Dpoly(int *f, int lenF) {
for (int i = 0; i < lenF; i++) f[i] = (LL)f[i + 1] * (i + 1) % P;
f[lenF] = 0;
}
void Jfpoly(int *f, int lenF) {
for (int i = lenF; i >= 0; i--) f[i + 1] = (LL)f[i] * sginv[i + 1] % P;
f[0] = 0;
}
void Lnpoly(int *f, int lenF) { // [0, lenF)
static int Inv_f[N << 2];
Invpoly(f, lenF, Inv_f), Dpoly(f, lenF - 1), Mulpoly(f, Inv_f, lenF - 1, lenF - 1), Jfpoly(f, lenF - 1);
for (int i = lenF; i <= (lenF << 2); i++) f[i] = 0;
}
void Exppoly(int *f, int lenF, int *g) { // [0, lenF)
static int s[N << 2];
int limit = 1; while (limit < lenF) limit <<= 1;
g[0] = 1;
for (int len = 2; len <= limit; len <<= 1) {
for (int i = (len >> 1); i < len; i++) g[i] = 0;
for (int i = 0; i < (len >> 1); i++) s[i] = g[i];
for (int i = (len >> 1); i < len; i++) s[i] = 0;
Lnpoly(s, len);
for (int i = 0; i < len; i++) s[i] = (f[i] - s[i] + P) % P;
s[0] = (s[0] + 1) % P, Mulpoly(g, s, len - 1, len - 1);
}
for (int i = lenF; i < limit; i++) g[i] = 0;
for (int i = 0; i < limit; i++) s[i] = 0;
}
}
int main() {
n = read();
for (int i = 0; i < n; i++) a[i] = read();
Poly::Getsginv(n << 2);
// Poly::Invpoly(a, n, b);
Poly::Exppoly(a, n, b);
// Poly::Lnpoly(a, n);
for (int i = 0; i < n; i++) printf("%d ", b[i]);
}