P5265 多项式反三角函数

P5265 多项式反三角函数

复合函数求导：
$$
(f \cdot g (x)) ^ {‘} = \frac {df} {dx} = \frac {df} {dg} \cdot \frac {dg} {dx} = f ^ {‘} (g(x)) g ^ {‘} (x)
$$
先考察反三角函数的导数：
$$
\begin {aligned}
& f(x) = arcsin(x) \\
\Longrightarrow & x = sin \cdot f(x) \\
\Longrightarrow & (x) ^ {‘} = [ sin \cdot f (x) ] ^ {‘} \\
\Longrightarrow & 1 = f ^ {‘} (x) cos \cdot f(x) \\
\end {aligned}
$$

$$
\begin {aligned}
\Longrightarrow f ^ {‘} (x) &= \frac 1 {cos \cdot f(x)} \\
&= \frac 1 {\sqrt{1 - sin ^ 2 \cdot f(x)}} \\
&= \frac 1 {\sqrt{1 - x ^ 2}}
\end {aligned}
$$

同理可证：$arctan ^ {‘} (x) = \frac 1 {1 + x ^ 2} $ 。
$$
\begin{aligned}
& g(x) = sin ^ {-1} f(x) \\
\Longrightarrow & g ^ {‘} (x) = \frac {f ^ {‘} (x)} {\sqrt {1 - f ^ 2(x)}} \\
\Longrightarrow & g(x) = \int \frac {f ^ {‘} (x)} {\sqrt {1 - f ^ 2(x)}} dx
\end{aligned}
$$

同理可证：$ tan ^ {-1} \cdot f(x) = \int \frac {f ^ {‘}} {1 + f ^ 2 (x)} dx$

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 4e5 + 10;
const LL mod = 998244353;
LL A[N];
int n, k, rev[N];
LL binpow(LL b, int k)
{
    LL res = 1;
    while (k)
    {
        if (k & 1)
            res = res * b % mod;
        b = b * b % mod;
        k >>= 1;
    }
    return res;
}
void PolyRev(int bit)
{
    for (int i = 1; i < (1 << bit); i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
}
void NTT(LL *x, int bit, int op)
{
    PolyRev(bit);
    int tot = 1 << bit;
    for (int i = 0; i < tot; i++)
        if (rev[i] < i)
            swap(x[i], x[rev[i]]);
    for (int mid = 1; mid < tot; mid <<= 1)
    {
        LL w1 = binpow(3, (mod - 1) / (mid << 1));
        if (op == -1)
            w1 = binpow(w1, mod - 2);
        for (int i = 0; i < tot; i += (mid << 1))
        {
            LL cur = 1;
            for (int j = 0; j < mid; j++, cur = cur * w1 % mod)
            {
                LL p = x[i + j], q = cur * x[i + j + mid] % mod;
                x[i + j] = (p + q) % mod, x[i + j + mid] = (p - q + mod) % mod;
            }
        }
    }
    if (op == -1)
    {
        LL intot = binpow(tot, mod - 2);
        for (int i = 0; i < tot; i++)
            x[i] = x[i] * intot % mod;
    }
}
void PolyInv(LL *x, LL *g, int len)
{
    if (len == 1)
    {
        g[0] = binpow(x[0], mod - 2);
        return;
    }
    int bit = 0;
    while ((1 << bit) < (len << 1))
        bit++;
    int tot = 1 << bit;
    PolyInv(x, g, len + 1 >> 1);
    static LL c[N];
    for (int i = (len + 1 >> 1); i < tot; i++)
        g[i] = 0;
    for (int i = 0; i < tot; i++)
        c[i] = (i < len ? x[i] : 0);
    NTT(g, bit, 1);
    NTT(c, bit, 1);
    for (int i = 0; i < tot; i++)
        g[i] = (2 - g[i] * c[i] % mod + mod) % mod * g[i] % mod;
    NTT(g, bit, -1);
    for (int i = len; i < tot; i++)
        g[i] = 0;
}
void PolyDerivate(LL *x, LL *g, int len)
{
    for (int i = 1; i < len; i++)
        g[i - 1] = x[i] * i % mod;
    g[len - 1] = 0;
}
void PolyIntegrate(LL *x, LL *g, int len)
{
    for (int i = 1; i < len; i++)
        g[i] = x[i - 1] * binpow(i, mod - 2) % mod;
    g[0] = 0;
}
void PolyLn(LL *x, LL *g, int len)
{
    static LL c[N], d[N];
    PolyDerivate(x, c, len);
    PolyInv(x, d, len);
    int bit = 0;
    while ((1 << bit) < (len << 1))
        bit++;
    int tot = 1 << bit;
    for (int i = len; i < tot; i++)
        c[i] = d[i] = 0;
    NTT(c, bit, 1);
    NTT(d, bit, 1);
    for (int i = 0; i < tot; i++)
        c[i] = c[i] * d[i] % mod;
    NTT(c, bit, -1);
    for (int i = len; i < tot; i++)
        c[i] = 0;
    PolyIntegrate(c, g, len);
    for (int i = len; i < tot; i++)
        g[i] = 0;
}
void PolyExp(LL *x, LL *g, int len)
{
    if (len == 1)
    {
        g[0] = 1;
        return;
    }
    int bit = 0;
    while ((1 << bit) < (len << 1))
        bit++;
    int tot = 1 << bit;
    PolyExp(x, g, len + 1 >> 1);
    static LL c[N];
    for (int i = 0; i < tot; i++)
        c[i] = 0;
    PolyLn(g, c, len);
    for (int i = 0; i < len; i++)
        c[i] = (x[i] - c[i] + mod) % mod;
    for (int i = len; i < tot; i++)
        c[i] = 0;
    c[0]++;
    NTT(g, bit, 1);
    NTT(c, bit, 1);
    for (int i = 0; i < tot; i++)
        g[i] = g[i] * c[i] % mod;
    NTT(g, bit, -1);
    for (int i = len; i < tot; i++)
        g[i] = 0;
}
void PolyBinpow(LL *x, LL *g, int k, int len)
{
    static LL c[N];
    PolyLn(x, c, len);
    for (int i = 0; i < n; i++)
        c[i] = c[i] * k;
    PolyExp(c, g, len);
}
void PolySqrt(LL *x, LL *g, int len)
{
    PolyBinpow(x, g, mod + 1 >> 1, len);
}
void PolyAsin(LL *x, LL *g, int len)
{
    static LL c[N], d[N], e[N];
    PolyDerivate(x, c, len);
    int bit = 0;
    while ((1 << bit) < (len << 1))
        bit++;
    int tot = 1 << bit;
    for (int i = 0; i < tot; i++)
        d[i] = i < len ? x[i] : 0;
    NTT(d, bit, 1);
    for (int i = 0; i < tot; i++)
        d[i] = d[i] * d[i] % mod;
    NTT(d, bit, -1);
    for (int i = 0; i < tot; i++)
        d[i] = i < len ? (!i - d[i] + mod) % mod : 0;
    PolySqrt(d, e, len);
    for (int i = 0; i < tot; i++)
        d[i] = 0;
    PolyInv(e, d, len);
    NTT(c, bit, 1);
    NTT(d, bit, 1);
    for (int i = 0; i < tot; i++)
        c[i] = c[i] * d[i] % mod;
    NTT(c, bit, -1);
    PolyIntegrate(c, g, len);
}
void PolyAtan(LL *x, LL *g, int len)
{
    static LL c[N], d[N], e[N];
    PolyDerivate(x, c, len);
    int bit = 0;
    while ((1 << bit) < (len << 1))
        bit++;
    int tot = 1 << bit;
    for (int i = 0; i < tot; i++)
        d[i] = i < len ? x[i] : 0;
    NTT(d, bit, 1);
    for (int i = 0; i < tot; i++)
        d[i] = d[i] * d[i] % mod;
    NTT(d, bit, -1);
    for (int i = 0; i < tot; i++)
        d[i] = i < len ? !i + d[i] : 0;
    PolyInv(d, e, len);
    NTT(c, bit, 1);
    NTT(e, bit, 1);
    for (int i = 0; i < tot; i++)
        c[i] = c[i] * e[i] % mod;
    NTT(c, bit, -1);
    PolyIntegrate(c, g, len);
}
int main()
{
    int op;
    scanf("%d%d", &n, &op);
    for (int i = 0; i < n; i++)
        scanf("%lld", &A[i]);
    static LL res[N];
    op ? PolyAtan(A, res, n) : PolyAsin(A, res, n);
    for (int i = 0; i < n; i++)
        printf("%lld ", res[i]);
    return 0;
}