多项式初等函数

本文转载（或修改）自 OI-Wiki

本页面包含多项式常见的初等函数操作。具体而言，本页面包含如下内容：

1. 多项式求逆
2. 多项式开方
3. 多项式除法
4. 多项式取模
5. 多项式指数函数
6. 多项式对数函数
7. 多项式快速幂
8. 多项式三角函数
9. 多项式反三角函数

初等函数与非初等函数

初等函数的定义如下：

若域 \(F\) 中存在映射 \(u\to \partial u\) 满足：

1. \(\partial(u+v)=\partial u+\partial v\)
2. \(\partial(uv)=u\partial v+v\partial u\)

则称这个域为 微分域。

若微分域 \(F\) 上的函数 \(u\) 满足以下的任意一条条件，则称该函数 \(u\) 为初等函数：

1. \(u\) 是 \(F\) 上的代数函数。
2. \(u\) 是 \(F\) 上的指数性函数，即存在 \(a\in F\) 使得 \(\partial u=u\partial a\) .
3. \(u\) 是 \(F\) 上的对数性函数，即存在 \(a\in F\) 使得 \(\partial u=\frac{\partial a}{a}\) .

以下是常见的初等函数：

1. 代数函数：存在有限次多项式 \(P\) 使得 \(P(f(x))=0\) 的函数 \(f(x)\)，如 \(2x+1\) , \(\sqrt{x}\) , \((1+x^2)^{-1}\) , \(|x|\) .
2. 指数函数
3. 对数函数
4. 三角函数
5. 反三角函数
6. 双曲函数
7. 反双曲函数

8. 以上函数的复合，如：

   \[ \frac{\mathrm{e}^{\tan x}}{1+x^2}\sin\left(\sqrt{1+\ln^2 x}\right) \]
   \[ -\mathrm{i} \ln\left(x+\mathrm{i}\sqrt{1-x^2}\right) \]

以下是常见的非初等函数：

1. 误差函数：

   \[ \operatorname{erf}(x):=\frac{2}{\sqrt{\pi}}\int_{0}^{x}\exp\left(-t^2\right)\mathrm{d}t \]

多项式求逆

P4238 【模板】多项式乘法逆

给定一个多项式 \(F(x)\) ，请求出一个多项式 \(G(x)\)， 满足 \(F(x) * G(x) \equiv 1 \pmod{x^n}\)。

系数对 \(998244353\) 取模。

对于 \(100\%\) 的数据，\(1 \leq n \leq 10^5\)， \(0 \leq a_i \leq 10^9\)。

首先，易知

\[ \left[x^{0}\right]f^{-1}\left(x\right)=\left(\left[x^{0}\right]f\left(x\right)\right)^{-1} \]

假设现在已经求出了 \(f\left(x\right)\) 在模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) 意义下的逆元 \(f^{-1}_{0}\left(x\right)\)。 有：

\[ \begin{aligned} f\left(x\right)f^{-1}_{0}\left(x\right)&\equiv 1 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ f\left(x\right)f^{-1}\left(x\right)&\equiv 1 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ f^{-1}\left(x\right)-f^{-1}_{0}\left(x\right)&\equiv 0 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} \end{aligned} \]

两边平方可得：

\[ f^{-2}\left(x\right)-2f^{-1}\left(x\right)f^{-1}_{0}\left(x\right)+f^{-2}_{0}\left(x\right)\equiv 0 \pmod{x^{n}} \]

两边同乘 \(f\left(x\right)\) 并移项可得：

\[ f^{-1}\left(x\right)\equiv f^{-1}_{0}\left(x\right)\left(2-f\left(x\right)f^{-1}_{0}\left(x\right)\right) \pmod{x^{n}} \]

递归计算即可，初始边界是 \(\left[x^{0}\right]f^{-1}\left(x\right)=\left(\left[x^{0}\right]f\left(x\right)\right)^{-1}\)，不过改成自底而上的迭代会好得多。

时间复杂度

\[ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right) \]

实现（迭代版）

void Inv(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    G[0] = inv(F[0]);
    int len, lim;
    for (len = 1; len < (n << 1); len <<= 1)
    {
        lim = len << 1;
        copy(F, F + len, A), copy(G, G + len, B);
        for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * len);
        NTT(A, lim, 1), NTT(B, lim, 1);
        for (int i = 0; i < lim; i++)
            G[i] = ((2 - A[i] * B[i] % p) * B[i] % p + p) % p;
        NTT(G, lim, -1);
        fill(G + len, G + lim, 0);
    }
    fill(A, A + len, 0), fill(B, B + len, 0), fill(G + n, G + len, 0);
}

多项式开方

P5205 【模板】多项式开根 P5277 【模板】多项式开根（加强版）

给定多项式 \(f\left(x\right)\)，求 \(g\left(x\right)\)，满足：

\[ g^{2}\left(x\right)\equiv f\left(x\right) \pmod{x^{n}} \]

普通版保证 \(f_0 = 1\)，加强版只保证 \(f_0\) 有二次剩余。

首先讨论 \(\left[x^0\right]f(x)\) 不为 \(0\) 的情况。

易知：

\[ \left[x^0\right]g(x) = \sqrt{\left[x^0\right]f(x)} \]

若 \(\left[x^0\right]f(x)\) 没有平方根，则多项式 \(f(x)\) 没有平方根。

\(\left[x^0\right]f(x)\) 可能有多个平方根，选取不同的根会求出不同的 \(g(x)\)。

假设现在已经求出了 \(f\left(x\right)\) 在模 \(x^{\left\lceil\frac{n}{2}\right\rceil}\) 意义下的平方根 \(g_{0}\left(x\right)\)，则有：

\[ \begin{aligned} g_{0}^{2}\left(x\right)&\equiv f\left(x\right) &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ g_{0}^{2}\left(x\right)-f\left(x\right)&\equiv 0 &\pmod{x^{\left\lceil\frac{n}{2}\right\rceil}}\\ \left(g_{0}^{2}\left(x\right)-f\left(x\right)\right)^{2}&\equiv 0 &\pmod{x^{n}}\\ \left(g_{0}^{2}\left(x\right)+f\left(x\right)\right)^{2}&\equiv 4g_{0}^{2}\left(x\right)f\left(x\right) &\pmod{x^{n}}\\ \left(\frac{g_{0}^{2}\left(x\right)+f\left(x\right)}{2g_{0}\left(x\right)}\right)^{2}&\equiv f\left(x\right) &\pmod{x^{n}}\\ \frac{g_{0}^{2}\left(x\right)+f\left(x\right)}{2g_{0}\left(x\right)}&\equiv g\left(x\right) &\pmod{x^{n}}\\ 2^{-1}g_{0}\left(x\right)+2^{-1}g_{0}^{-1}\left(x\right)f\left(x\right)&\equiv g\left(x\right) &\pmod{x^{n}} \end{aligned} \]

倍增计算即可。

时间复杂度

\[ T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n\log{n}\right)=O\left(n\log{n}\right) \]

还有一种常数较小的写法就是在倍增维护 \(g\left(x\right)\) 的时候同时维护 \(g^{-1}\left(x\right)\) 而不是每次都求逆。

当 \(\left[x^{0}\right]f\left(x\right)\neq 1\) 时，可能需要使用二次剩余来计算 \(\left[x^{0}\right]g\left(x\right)\)。

上述方法需要知道 \(g_{0}(x)\) 的逆，所以常数项不能为 \(0\)。

若 \(\left[x^0\right]f(x) = 0\)，则将 \(f(x)\) 分解成 \(x^{k}h(x)\)，其中 \(\left[x^0\right]h(x) \not = 0\)。

• 若 \(k\) 是奇数，则 \(f(x)\) 没有平方根。
• 若 \(k\) 是偶数，则求出 \(h(x)\) 的平方根 \(\sqrt{h(x)}\)，然后得到 \(g(x) \equiv x^{k/2} \sqrt{h(x)} \pmod{x^{n}}\)。

实现

普通版加强版

void Sqrt(ll *F, ll *G, int n) // G = sqrt(F)
{
    static const ll inv2 = inv(2);
    G[0] = 1;
    static ll A[MAXN], B[MAXN];
    int len, lim;
    for (len = 1; len < (n << 1); len <<= 1)
    {
        lim = len << 1;
        copy(F, F + len, A);
        Inv(G, B, len);
        for (int i = 0; i < lim; i++)
            rev[i] = (rev[i >> 1] >> 1) | ((lim >> 1) * (i & 1));
        NTT(A, lim, 1), NTT(B, lim, 1);
        for (int i = 0; i < lim; i++) A[i] = A[i] * B[i] % p;
        NTT(A, lim, -1);
        for (int i = 0; i < len; i++) G[i] = (G[i] + A[i]) % p * inv2 % p;
        fill(G + len, G + lim, 0);
    }
    fill(A, A + len, 0), fill(B, B + len, 0), fill(G + n, G + len, 0);
}

void Sqrt(ll *F, ll *G, int n)
{
    static const ll inv2 = inv(2);
    ll x1, x2;
    cipolla::cipolla(F[0], x1, x2);
    G[0] = min(x1, x2);
    static ll A[MAXN], B[MAXN];
    int len, lim;
    for (len = 1; len < (n << 1); len <<= 1)
    {
        lim = len << 1;
        copy(F, F + len, A);
        Inv(G, B, len);
        for (int i = 0; i < lim; i++)
            rev[i] = (rev[i >> 1] >> 1) | ((lim >> 1) * (i & 1));
        NTT(A, lim, 1), NTT(B, lim, 1);
        for (int i = 0; i < lim; i++) A[i] = A[i] * B[i] % p;
        NTT(A, lim, -1);
        for (int i = 0; i < len; i++) G[i] = (G[i] + A[i]) % p * inv2 % p;
        fill(G + len, G + lim, 0);
    }
    fill(A, A + len, 0), fill(B, B + len, 0), fill(G + n, G + len, 0);
}

多项式除法 & 取模

P4512 【模板】多项式除法

给定多项式 \(F\left(x\right),G\left(x\right)\)，求 \(G\left(x\right) \div F\left(x\right)\) 的商式 \(Q\left(x\right)\) 和余式 \(R\left(x\right)\)。

发现若能消除 \(R\left(x\right)\) 的影响则可直接 多项式求逆 解决。

具体来说，设多项式 \(A\) 为 \(n\) 次多项式，考虑一种操作 \(R\)，使得

\[A_R(x) = x^n A\left(\frac{1}{x}\right)\]

稍微想象一下，可以发现 \(A_R[i] = A[n - i]\)（ \([i]\) 表示多项式的第 \(i\) 次系数）。这个操作可以 \(O(n)\) 完成。

然后开始推式子：

\[\begin{aligned} F(x) &= Q(x) * G(x) + R(x) \\ F\left(\frac{1}{x}\right) &= Q\left(\frac{1}{x}\right) * G\left(\frac{1}{x}\right) + R\left(\frac{1}{x}\right) \\ x^n F\left(\frac{1}{x}\right) &= x^{n - m} Q\left(\frac{1}{x}\right) * x^m G\left(\frac{1}{x}\right) + x^{n - m + 1} * x^{m - 1} R\left(\frac{1}{x}\right) \\ F_R(x) &= Q_R(x) * G_R(x) + x^{n - m + 1} * R_R(x) \\ F_R(x) &\equiv Q_R(x) * G_R(x) + x^{n - m + 1} * R_R(x) \pmod{x^{n-m+1}} \\ F_R(x) &\equiv Q_R(x) * G_R(x) \pmod{x^{n-m+1}} \\ Q_R(x) &\equiv F_R(x) * G_R^{-1}(x) \pmod{x^{n-m+1}} \end{aligned}\]

求一遍 \(G_R\) 的逆，然后就可以利用多项式乘法求出 \(Q\)。然后

\[R(x) = F(x) - G(x) * Q(x)\]

直接计算即可。时间复杂度 \(O(n \log n)\)。

时间复杂度 \(O\left(n\log{n}\right)\)。

实现

void Div(ll *F, ll *G, ll *Q, ll *R, int n, int m)
{
    static ll B[MAXN], BR[MAXN], A[MAXN];
    static int lim;
    for (lim = 1; lim < (n << 1); lim <<= 1);
    copy(G, G + m, B), reverse(B, B + m), Inv(n, B, BR);
    for (lim = 1; lim < (n << 1); lim <<= 1);
    copy(F, F + n, B), reverse(B, B + n);
    NTT(B, lim, 1), NTT(BR, lim, 1);
    for (int i = 0; i < lim; i++) Q[i] = B[i] * BR[i] % p;
    NTT(Q, lim, -1), fill(Q + n - m + 1, Q + lim, 0), reverse(Q, Q + n - m + 1),
        fill(B, B + lim, 0), fill(BR, BR + lim, 0), copy(Q, Q + n - m + 1, A),
        copy(G, G + m, B), NTT(A, lim, 1), NTT(B, lim, 1);
    for (int i = 0; i < lim; i++) A[i] = A[i] * B[i] % p;
    NTT(A, lim, -1);
    for (int i = 0; i < m - 1; i++) R[i] = (F[i] + p - A[i]) % p;
    fill(B, B + lim, 0), fill(BR, BR + lim, 0), fill(A, A + lim, 0);
}

多项式对数函数

P4725 【模板】多项式对数函数（多项式 ln）

给定多项式 \(f(x)\)，求模 \(x^{n}\) 意义下的 \(\ln{f(x)}\)。

首先，对于多项式 \(f(x)\)，若 \(\ln{f(x)}\) 存在，则由其定义，其必须满足：

\[ [x^{0}]f(x)=1 \]

对 \(\ln{f(x)}\) 求导再积分，可得：

\[ \begin{aligned} \frac{\mathrm{d} \ln{f(x)}}{\mathrm{d} x} & \equiv \frac{f'(x)}{f(x)} & \pmod{x^{n}} \\ \ln{f(x)} & \equiv \int\frac{f'(x)}{f(x)} \mathrm{d} x & \pmod{x^{n}} \end{aligned} \]

多项式的求导，积分时间复杂度为 \(O(n)\)，求逆时间复杂度为 \(O(n\log{n})\)，故多项式求 \(\ln\) 时间复杂度 \(O(n\log{n})\)。

实现

void Ln(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    Inv(n, F, A), Dert(n, F, B);
    int lim;
    for (lim = 1; lim < (n << 1); lim <<= 1);
    for (int i = 0; i < lim; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
    NTT(A, lim, 1), NTT(B, lim, 1);
    for (int i = 0; i < lim; i++) A[i] = A[i] * B[i] % p;
    NTT(A, lim, -1), fill(A + n, A + lim, 0), Int(n - 1, A, G), fill(A, A + lim, 0), fill(B, B + lim, 0);
}

多项式指数函数

P4726 【模板】多项式指数函数（多项式 exp）

给定多项式 \(f(x)\)，求模 \(x^{n}\) 意义下的 \(\exp{f(x)}\)。

首先，对于多项式 \(f(x)\)，若 \(\exp{f(x)}\) 存在，则其必须满足：

\[ [x^{0}]f(x)=0 \]

否则 \(\exp{f(x)}\) 的常数项不收敛。

对 \(\exp{f(x)}\) 求导，可得：

\[ \frac{\mathrm{d} \exp{f(x)}}{\mathrm{d} x} \equiv \exp{f(x)}f'(x)\pmod{x^{n}} \]

比较两边系数可得：

\[ [x^{n-1}]\frac{\mathrm{d} \exp{f(x)}}{\mathrm{d} x} = \sum_{i = 0}^{n - 1} \left([x^{i}]\exp{f(x)}\right) \left([x^{n-i-1}]f'(x)\right) \]

\[ n[x^{n}]\exp{f(x)} = \sum_{i = 0}^{n - 1} \left([x^{i}]\exp{f(x)}\right) \left((n - i)[x^{n - i}]f(x)\right) \]

使用分治 FFT 即可解决。

时间复杂度 \(O(n\log^{2}{n})\)。

更加常见且快速的做法是应用 Newton's Method，时间复杂度 \(O(n\log n)\)，下面是其实现：

实现

void Exp(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    int lim, len;
    G[0] = 1;
    for (len = 1; len < (n << 1); len <<= 1)
    {
        lim = len << 1;
        copy(F, F + len, A), Ln(len, G, B);
        for (int i = 0; i < lim; i++)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * len);
        NTT(A, lim, 1), NTT(B, lim, 1), NTT(G, lim, 1);
        for (int i = 0; i < lim; i++)
            G[i] = (1 - B[i] + A[i] + p) % p * G[i] % p;
        NTT(G, lim, -1), fill(A, A + lim, 0), fill(B, B + lim, 0);
    }
    fill(G + n, G + len, 0);
}

多项式快速幂

P5245 【模板】多项式快速幂 P5273 【模板】多项式快速幂（加强版）

计算 \(f^{k}(x)\)

普通做法为直接套用实数域中的快速幂，时间复杂度 \(O(n\log{n}\log{k})\)，不够优秀，Luogu上的板子中，\(k = 10^{10^{15}}\)。

（普通版）当 \([x^{0}]f(x)=1\) 时，有：

\[f^{k}(x)=\exp{\left(k\ln{f(x)}\right)}\]

（加强版）当 \([x^{0}]f(x)\neq 1\) 时，设 \(f(x)\) 的最低次项为 \(f_{i}x^{i}\)，则：

\[f^{k}(x)=f_{i}^{k}x^{ik}\exp{\left(k\ln{\frac{f(x)}{f_{i}x^{i}}}\right)}\]

时间复杂度 \(O(n\log{n})\)。

实现

普通版加强版

void Pow(int n, ll k, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    copy(F, F + n, A);
    Ln(n, A, B);
    for (int i = 0; i < n; i++)
        B[i] = B[i] * k % p;
    Exp(n, B, G), fill(A, A + n, 0), fill(B, B + n, 0);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    initinv(4e5);
    cin >> n >> sk;
    for (char ch : sk)
        k = (k * 10 % p + (ch ^ 48)) % p;
    for (int i = 0; i < n; i++)
        cin >> F[i];
    Pow(n, k, F, G);
    for (int i = 0; i < n; i++)
        cout << G[i] << " ";
    return 0;
}

void Pow(ll n, ll k, ll k2, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    ll t = 0;
    while (t < n && !F[t]) t++;
    copy(F + t, F + n, A);
    ll m = n - t;
    ll f0 = A[0], invf0 = getinv(f0), pf0 = qpow(f0, k2);
    for (ll i = 0; i < m; i++) A[i] = A[i] * invf0 % p;
    Ln(m, A, B);
    for (ll i = 0; i < m; i++) B[i] = B[i] * k % p;
    fill(A, A + m, 0), Exp(m, B, A), t *= k2;
    for (ll i = n - t - 1; i >= 0; i--) G[i + t] = A[i] * pf0 % p;
    fill(A, A + m, 0), fill(B, B + m, 0);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    initinv(4e6);
    cin >> n >> sk;
    for (char ch : sk)
        k = (k * 10 % p + (ch ^ 48)) % p,
        k2 = (k2 * 10 % (p - 1) + (ch ^ 48)) % (p - 1);
    for (int i = 0; i < n; i++) cin >> F[i];
    if (!(F[0] == 0 && sk.size() > log10(n) + 1)) Pow(n, k, k2, F, G);
    for (int i = 0; i < n; i++) cout << G[i] << " ";
    return 0;
}

多项式三角函数

P5264 多项式三角函数

给定多项式 \(f\left(x\right)\)，求模 \(x^{n}\) 意义下的 \(\sin{f\left(x\right)}\) 与 \(\cos{f\left(x\right)}\)。

首先由欧拉公式 \(\left(\mathrm{e}^{\mathrm{i}x} = \cos{x} + \mathrm{i}\sin{x}\right)\) 可以得到三角函数的另一个表达式

\[ \begin{aligned} \sin{x} &= \frac{\mathrm{e}^{\mathrm{i}x} - \mathrm{e}^{-\mathrm{i}x}}{2\mathrm{i}} \\ \cos{x} &= \frac{\mathrm{e}^{\mathrm{i}x} + \mathrm{e}^{-\mathrm{i}x}}{2} \end{aligned} \]

那么代入 \(f\left(x\right)\) 就有：

\[ \begin{aligned} \sin{f\left(x\right)} &= \frac{\exp{\left(\mathrm{i}f\left(x\right)\right)} - \exp{\left(-\mathrm{i}f\left(x\right)\right)}}{2\mathrm{i}} \\ \cos{f\left(x\right)} &= \frac{\exp{\left(\mathrm{i}f\left(x\right)\right)} + \exp{\left(-\mathrm{i}f\left(x\right)\right)}}{2} \end{aligned} \]

直接按上述表达式编写程序即可得到模 \(x^{n}\) 意义下的 \(\sin{f\left(x\right)}\) 与 \(\cos{f\left(x\right)}\)。再由 \(\tan{f\left(x\right)} = \frac{\sin{f\left(x\right)}}{\cos{f\left(x\right)}}\) 可求得 \(\tan{f\left(x\right)}\)。

模意义下的虚数

注意到我们是在 \(\mathbb{Z}_{998244353}\) 上做 NTT，那么相应地，虚数单位 \(\mathrm{i}\) 应该被换成 \(86583718\) （或 \(911660635\)）：

\[ \begin{aligned} & \mathrm{i} = \sqrt{-1} \equiv \sqrt{998244352} \pmod{998244353} \\ \implies & \phantom{\text{or}} \quad \mathrm{i} \equiv 86583718 \pmod{998244353} \end{aligned} \]

对应 \(g^{\frac{p - 1}{4}}\)。

实现

const ll Imag = getinv((p - 1) / 4);
void Sin(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN], H[MAXN];
    for (int i = 0; i < n; i++) A[i] = F[i] * Imag;
    Exp(n, A, B), Inv(n, B, H);
    static ll inv2imag = getinv(2 * Imag);
    for (int i = 0; i < n; i++) G[i] = (B[i] - H[i] + p) % p * inv2imag % p;
    fill(A, A + n, 0), fill(B, B + n, 0), fill(H, H + n, 0);
}
void Cos(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN], H[MAXN];
    for (int i = 0; i < n; i++) A[i] = F[i] * Imag;
    Exp(n, A, B), Inv(n, B, H);
    static ll inv2 = getinv(2);
    for (int i = 0; i < n; i++) G[i] = (B[i] + H[i]) % p * inv2 % p;
    fill(A, A + n, 0), fill(B, B + n, 0), fill(H, H + n, 0);
}

多项式反三角函数

P5265 多项式反三角函数

给定多项式 \(f\left(x\right)\)，求模 \(x^{n}\) 意义下的 \(\arcsin{f\left(x\right)}\) 与 \(\arctan{f\left(x\right)}\)。

仿照求多项式 \(\ln\) 的方法，对反三角函数求导再积分可得：

\[ \begin{aligned} \frac{\mathrm{d}}{\mathrm{d} x} \arcsin{x} &= \frac{1}{\sqrt{1 - x^{2}}} \\ \arcsin{x} &= \int \frac{1}{\sqrt{1 - x^{2}}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arccos{x} &= - \frac{1}{\sqrt{1 - x^{2}}} \\ \arccos{x} &= - \int \frac{1}{\sqrt{1 - x^{2}}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arctan{x} &= \frac{1}{1 + x^{2}} \\ \arctan{x} &= \int \frac{1}{1 + x^{2}} \mathrm{d} x \end{aligned} \]

那么代入 \(f\left(x\right)\) 就有：

\[ \begin{aligned} \frac{\mathrm{d}}{\mathrm{d} x} \arcsin{f\left(x\right)} &= \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \\ \arcsin{f\left(x\right)} &= \int \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arccos{f\left(x\right)} &= - \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \\ \arccos{f\left(x\right)} &= - \int \frac{f'\left(x\right)}{\sqrt{1 - f^{2}\left(x\right)}} \mathrm{d} x \\ \frac{\mathrm{d}}{\mathrm{d} x} \arctan{f\left(x\right)} &= \frac{f'\left(x\right)}{1 + f^{2}\left(x\right)} \\ \arctan{f\left(x\right)} &= \int \frac{f'\left(x\right)}{1 + f^{2}\left(x\right)} \mathrm{d} x \end{aligned} \]

直接按式子求就可以了。（我也不清楚Luogu凭什么给这个玩意评黑）

实现

void Asin(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    copy(F, F + n, A);
    int lim;
    for (lim = 1; lim < (n << 1); lim <<= 1);
    for (int i = 0; i < lim; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
    NTT(A, lim, 1);
    for (int i = 0; i < lim; i++) A[i] = A[i] * A[i] % p;
    NTT(A, lim, -1), fill(A + n, A + lim, 0);
    for (int i = 0; i < n; i++) A[i] = (p - A[i]) % p;
    A[0] = (A[0] + 1) % p, Sqrt(n, A, B), fill(A, A + n, 0), Inv(n, B, A),
    fill(B, B + n, 0), Dert(n, F, B);
    for (int i = 0; i < lim; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
    NTT(A, lim, 1), NTT(B, lim, 1);
    for (int i = 0; i < lim; i++) A[i] = A[i] * B[i] % p;
    NTT(A, lim, -1), fill(A + n, A + lim, 0), fill(B, B + lim, 0), Int(n, A, G),
        fill(A, A + n, 0);
}
void Atan(int n, ll *F, ll *G)
{
    static ll A[MAXN], B[MAXN];
    copy(F, F + n, A);
    int lim;
    for (lim = 1; lim < (n << 1); lim <<= 1);
    for (int i = 0; i < lim; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
    NTT(A, lim, 1);
    for (int i = 0; i < lim; i++) A[i] = A[i] * A[i] % p;
    NTT(A, lim, -1), fill(A + n, A + lim, 0),
        A[0] = (A[0] + 1) % p, Inv(n, A, B), fill(A, A + n, 0), Dert(n, F, A);
    for (int i = 0; i < lim; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
    NTT(A, lim, 1), NTT(B, lim, 1);
    for (int i = 0; i < lim; i++) A[i] = A[i] * B[i] % p;
    NTT(A, lim, -1), fill(A + n, A + lim, 0), fill(B, B + lim, 0), Int(n, A, G),
        fill(A, A + n, 0);
}

总结

下面的代码实现了 Poly 类，实现了本页面的所有操作，经过了 GPT 的优化。

实现

#ifndef MPOLY_HPP
#define MPOLY_HPP
#include <bits/stdc++.h>
using namespace std;
#ifndef rep
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#endif
template <int P = 998244353, int G = 3, int ML = 22>
struct Poly : vector<int> {
    using vector<int>::vector;
    using ll = long long;
    using T = Poly<P, G, ML>;
    static constexpr int mod = P;
    static constexpr int root = G;
    static constexpr int ml = ML;
    static_assert(P > 2 && P < (1 << 30));
    static_assert((P - 1LL) % (1LL << ML) == 0);
    static inline int rt[ML + 1];
    static inline int irt[ML + 1];
    static inline int invn[1 << ML];
    static inline int invflg = 1;
    static inline bool inited = false;
    static inline int qpow(int a, long long b) {
        int r = 1;
        for (; b; b >>= 1, a = (ll)a * a % P)
            if (b & 1) r = (ll)r * a % P;
        return r;
    }
    static inline void init() {
        if (inited) return;
        inited = true;
        rep(k, 1, ML) {
            rt[k] = qpow(G, (P - 1LL) >> k);
            irt[k] = qpow(rt[k], P - 2LL);
        }
        invn[1] = 1;
    }
    static inline void initInv(int n) {
        init();
        if (n <= invflg) return;
        n = min(n, P - 1);
        rep(i, invflg + 1, n)
            invn[i] = P - (ll)(P / i) * invn[P % i] % P;
        invflg = n;
    }
    static inline int norm(ll x) {
        x %= P;
        if (x < 0) x += P;
        return (int)x;
    }
    static inline int lim(int n) {
        int z = 1;
        while (z < n) z <<= 1;
        return z;
    }
    static inline void NTT(T &a, bool iv = false) {
        init();
        const int n = (int)a.size();
        if (n <= 1) return;
        if (!iv) {
            for (int len = n, k = __builtin_ctz((unsigned)len); len > 1; len >>= 1, --k) {
                const int half = len >> 1;
                const int wlen = rt[k];
                for (int l = 0; l < n; l += len) {
                    int w = 1;
                    for (int i = 0; i < half; ++i) {
                        const int x = a[l + i];
                        const int y = a[l + i + half];
                        int u = x + y;
                        if (u >= P) u -= P;
                        int v = x - y;
                        if (v < 0) v += P;
                        a[l + i] = u;
                        a[l + i + half] = (ll)v * w % P;
                        w = (ll)w * wlen % P;
                    }
                }
            }
        } else {
            for (int len = 2, k = 1; len <= n; len <<= 1, ++k) {
                const int half = len >> 1;
                const int wlen = irt[k];
                for (int l = 0; l < n; l += len) {
                    int w = 1;
                    for (int i = 0; i < half; ++i) {
                        const int x = a[l + i];
                        const int v = (ll)a[l + i + half] * w % P;
                        int u = x + v;
                        if (u >= P) u -= P;
                        int d = x - v;
                        if (d < 0) d += P;
                        a[l + i] = u;
                        a[l + i + half] = d;
                        w = (ll)w * wlen % P;
                    }
                }
            }
            initInv(n);
            const int iv = invn[n];
            for (int &x : a) x = (ll)x * iv % P;
        }
    }
    static inline void trim(T &a) {
        while (!a.empty() && a.back() == 0) a.pop_back();
    }
    static inline T modXn(T a, int n) {
        if ((int)a.size() > n) a.resize(n);
        return a;
    }
    static inline void read(int n, T &a) {
        a.resize(n);
        for (int &x : a) cin >> x, x = norm(x);
    }
    static inline T read(int n) {
        T a;
        read(n, a);
        return a;
    }
    static inline void write(const T &a) {
        for (int x : a) cout << x << ' ';
        cout << '\n';
    }
    friend inline T operator+(T a, const T &b) {
        if (a.size() < b.size()) a.resize(b.size());
        rep(i, 0, (int)b.size() - 1) {
            int x = a[i] + b[i];
            if (x >= P) x -= P;
            a[i] = x;
        }
        return a;
    }
    friend inline T operator-(T a, const T &b) {
        if (a.size() < b.size()) a.resize(b.size());
        rep(i, 0, (int)b.size() - 1) {
            int x = a[i] - b[i];
            if (x < 0) x += P;
            a[i] = x;
        }
        return a;
    }
    friend inline T operator*(T a, int x) {
        x = norm(x);
        if (x == 0) return T(a.size(), 0);
        if (x == 1) return a;
        for (int &y : a) y = (ll)y * x % P;
        return a;
    }
    friend inline T operator*(int x, T a) { return a * x; }
    friend inline T operator/(T a, int x) {
        x = norm(x);
        assert(x);
        return a * qpow(x, P - 2LL);
    }
    friend inline T operator/(const T &a, const T &b) { return Div(a, b); }
    friend inline T operator%(const T &a, const T &b) { return Mod(a, b); }
    static inline T sqr(const T &a) {
        const int n = (int)a.size();
        if (!n) return {};
        if (n <= 32) {
            T c(2 * n - 1);
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    c[i + j] = (c[i + j] + (ll)a[i] * a[j]) % P;
            return c;
        }
        const int z = lim(2 * n - 1);
        T c(a);
        c.resize(z);
        NTT(c);
        for (int &x : c) x = (ll)x * x % P;
        NTT(c, true);
        c.resize(2 * n - 1);
        return c;
    }
    friend inline T operator*(const T &a, const T &b) {
        const int n = (int)a.size(), m = (int)b.size();
        if (!n || !m) return {};
        if (&a == &b) return sqr(a);
        if (1LL * min(n, m) * max(n, m) <= 4096 || min(n, m) <= 16) {
            T c(n + m - 1);
            if (n < m) {
                for (int i = 0; i < n; ++i)
                    for (int j = 0; j < m; ++j)
                        c[i + j] = (c[i + j] + (ll)a[i] * b[j]) % P;
            } else {
                for (int i = 0; i < m; ++i)
                    for (int j = 0; j < n; ++j)
                        c[i + j] = (c[i + j] + (ll)b[i] * a[j]) % P;
            }
            return c;
        }
        const int z = lim(n + m - 1);
        T A(a), B(b);
        A.resize(z), B.resize(z);
        NTT(A), NTT(B);
        for (int i = 0; i < z; ++i) A[i] = (ll)A[i] * B[i] % P;
        NTT(A, true);
        A.resize(n + m - 1);
        return A;
    }
    static inline T Dert(const T &a) {
        const int n = (int)a.size();
        if (n <= 1) return {};
        T b(n - 1);
        for (int i = 1; i < n; ++i) b[i - 1] = (ll)a[i] * i % P;
        return b;
    }
    static inline T Int(const T &a) {
        const int n = (int)a.size();
        T b(n + 1);
        if (n) {
            initInv(n);
            for (int i = 0; i < n; ++i) b[i + 1] = (ll)a[i] * invn[i + 1] % P;
        }
        return b;
    }
    static inline T Inv(const T &f, int n) {
        assert(!f.empty() && f[0]);
        if (n <= 0) return {};
        if (n == 1) return T{qpow(f[0], P - 2LL)};
        T g{qpow(f[0], P - 2LL)};
        int len = 1;
        while (len < n) {
            const int need = min(n, len << 1);
            const int z = lim(need + (len << 1) - 1);
            T a(f.begin(), f.begin() + min((int)f.size(), need));
            T b(g);
            a.resize(z), b.resize(z);
            NTT(a), NTT(b);
            for (int i = 0; i < z; ++i) {
                int t = b[i] + b[i];
                if (t >= P) t -= P;
                t -= (ll)a[i] * b[i] % P * b[i] % P;
                if (t < 0) t += P;
                b[i] = t;
            }
            NTT(b, true);
            b.resize(need);
            g.swap(b);
            len = need;
        }
        return g;
    }
    static inline T Inv(const T &f) { return Inv(f, (int)f.size()); }
    static inline void Div(const T &f, const T &g, T &q, T &r) {
        assert(!g.empty() && g.back());
        if (f.size() < g.size()) {
            q.clear();
            r = f;
            return;
        }
        const int n = (int)f.size(), m = (int)g.size(), k = n - m + 1;
        T a(f.rbegin(), f.rend()), b(g.rbegin(), g.rend());
        a.resize(k), b.resize(k);
        q = a * Inv(b, k);
        q.resize(k);
        reverse(q.begin(), q.end());
        r = f - g * q;
        r.resize(m - 1);
    }
    static inline T Div(const T &f, const T &g) {
        T q, r;
        Div(f, g, q, r);
        return q;
    }
    static inline T Mod(const T &f, const T &g) {
        T q, r;
        Div(f, g, q, r);
        return r;
    }
    static inline T Ln(const T &f) {
        const int n = (int)f.size();
        assert(n && f[0] == 1);
        if (n == 1) return T{};
        T d = Dert(f);
        d = d * Inv(f, n - 1);
        d.resize(n - 1);
        return Int(d);
    }
    static inline T Exp(const T &f) {
        const int n = (int)f.size();
        assert(n && f[0] == 0);
        if (n == 1) return T{1};
        T g{1};
        for (int len = 1; len < n; len <<= 1) {
            const int need = min(n, len << 1);
            T h(g);
            h.resize(need);
            T lf = Ln(h);
            if ((int)f.size() >= need) {
                for (int i = 0; i < need; ++i) {
                    int x = f[i] - lf[i];
                    if (x < 0) x += P;
                    lf[i] = x;
                }
            } else {
                for (int i = 0; i < (int)f.size(); ++i) {
                    int x = f[i] - lf[i];
                    if (x < 0) x += P;
                    lf[i] = x;
                }
            }
            ++lf[0];
            g = g * lf;
            g.resize(need);
        }
        g.resize(n);
        return g;
    }
    static inline int sqrtx(int a) {
        a = norm(a);
        if (!a) return 0;
        if (qpow(a, (P - 1LL) >> 1) != 1) return -1;
        if ((P & 3) == 3) return qpow(a, (P + 1LL) >> 2);
        int q = P - 1, s = 0;
        while (!(q & 1)) q >>= 1, ++s;
        int z = 2;
        while (qpow(z, (P - 1LL) >> 1) != P - 1) ++z;
        int c = qpow(z, q), x = qpow(a, (q + 1LL) >> 1), t = qpow(a, q);
        int m = s;
        while (t != 1) {
            int i = 1;
            int tt = (ll)t * t % P;
            while (tt != 1) tt = (ll)tt * tt % P, ++i;
            int b = qpow(c, 1LL << (m - i - 1));
            x = (ll)x * b % P;
            t = (ll)t * b % P * b % P;
            c = (ll)b * b % P;
            m = i;
        }
        return x;
    }
    static inline T Sqrt(const T &f) {
        const int n = (int)f.size();
        assert(n);
        int s = sqrtx(f[0]);
        assert(s != -1);
        if (!f[0]) {
            int p = 0;
            while (p < n && !f[p]) ++p;
            if (p == n) return T(n, 0);
            if (p & 1) return {};
            T h(f.begin() + p, f.end());
            h = Sqrt(h);
            T g(n, 0);
            const int sh = p >> 1;
            for (int i = 0; i < (int)h.size() && i + sh < n; ++i) g[i + sh] = h[i];
            return g;
        }
        const int inv2 = (P + 1) >> 1;
        T g{min(s, P - s)};
        for (int len = 1; len < n; len <<= 1) {
            const int need = min(n, len << 1);
            T h(f.begin(), f.begin() + need);
            h = h * Inv(g, need);
            h.resize(need);
            g.resize(need);
            for (int i = 0; i < need; ++i) {
                int x = g[i] + h[i];
                if (x >= P) x -= P;
                g[i] = (ll)x * inv2 % P;
            }
        }
        g.resize(n);
        return g;
    }
    static inline T Pow(T f, long long k) {
        const int n = (int)f.size();
        if (!n) return {};
        if (k == 0) return T(n, 0) + T{1};
        unsigned long long e;
        if (k < 0) {
            f = Inv(f);
            e = 0ULL - (unsigned long long)k;
        } else {
            e = (unsigned long long)k;
        }
        int t = 0;
        while (t < n && f[t] == 0) ++t;
        if (t == n || (unsigned long long)t * e >= (unsigned long long)n) return T(n, 0);
        const int m = n - (int)((unsigned long long)t * e);
        const int c = f[t];
        const int ic = qpow(c, P - 2LL);
        T g(f.begin() + t, f.end());
        for (int &x : g) x = (ll)x * ic % P;
        g.resize(m);
        g = Exp(Ln(g) * (int)(e % P));
        const int ck = qpow(c, e % (P - 1LL));
        T res(n, 0);
        for (int i = 0; i < m; ++i) res[i + t * e] = (ll)g[i] * ck % P;
        return res;
    }
    static inline int iv() {
        static const int i = [] {
            int x = sqrtx(P - 1);
            assert(x != -1);
            return x;
        }();
        return i;
    }
    static inline T Sin(const T &f) {
        const int im = iv();
        const int inv2im = qpow((ll)2 * im % P, P - 2LL);
        return (Exp(f * im) - Exp(f * (P - im))) * inv2im;
    }
    static inline T Cos(const T &f) {
        const int im = iv();
        const int inv2 = (P + 1) >> 1;
        return (Exp(f * im) + Exp(f * (P - im))) * inv2;
    }
    static inline T Asin(const T &f) {
        assert(!f.empty() && f[0] == 0);
        if (f.size() == 1) return T{0};
        T g = T{1} - sqr(f);
        g.resize(f.size());
        g = Inv(Sqrt(g), (int)f.size());
        g = Dert(f) * g;
        g.resize((int)f.size() - 1);
        return Int(g);
    }
    static inline T Atan(const T &f) {
        assert(!f.empty() && f[0] == 0);
        if (f.size() == 1) return T{0};
        T g = T{1} + sqr(f);
        g.resize(f.size());
        g = Inv(g, (int)f.size());
        g = Dert(f) * g;
        g.resize((int)f.size() - 1);
        return Int(g);
    }
};
#ifdef rep
#undef rep
#endif
#endif