概述

给定一个 $n - 1$ 次多项式 $A(x)$，你需要求出多项式 $B(x)$ 满足 $B(x) \equiv \sin A(x) \pmod{x ^n}$ 或 $B(x) \equiv \cos A(x) \pmod{x ^ n}$。

思路

首先我们有欧拉公式：

$$ e ^ {i \theta} = \cos \theta + i \sin \theta $$

稍作变换得到：

$$ e ^ {-i \theta} = \cos \theta - i \sin \theta $$

我们将 $\theta$ 用 $A(x)$ 代替，并将两式分别加减，得到：

$$ \sin A(x) = \frac{e ^ {i \theta} - e ^ {-i \theta}}{2i} \\ \cos A(x) = \frac{e ^ {i \theta} + e ^ {-i \theta}}{2} $$

直接套用多项式 $\exp$ 和求逆的板子即可。

求解

这里提几个实现上的要点。

1. 由于 $e ^ {-i \theta} = \left(e ^ {i \theta}\right) ^ {-1}$，因此只需要进行一次 $\exp$，可以获得很大的常数优化。
2. 所有多项式操作都是基于整数的，但是这里出现了虚数 $i = \sqrt{-1}$。我们需要计算 $-1$ 在模意义下的二次剩余。

代码

Vec sin(Vec A) {
    assert(A[0] == 0);
    int i = degree(MOD - 1, 2, MOD);
    Vec E = exp(i * A);
    return (E - ~E) / (2LL * i % MOD);
}
Vec cos(Vec A) {
    assert(A[0] == 0);
    int i = degree(MOD - 1, 2, MOD);
    Vec E = exp(i * A);
    return (E + ~E) / 2;
}
Vec tan(Vec A) {
    assert(A[0] == 0);
    int n = A.size();
    return fix(sin(A) * ~cos(A), n);
}