「Learning Notes」多项式三角函数

本文会随着笔者的水平提升持续更新.
若发现文中有叙述不严谨之处,欢迎指出。

Description

给定多项式 f(x) ,求模 x^{n} 意义下的 \sin{f(x)}, \cos{f(x)} \tan{f(x)}

Method

首先由 Euler's formula \left(e^{ix} = \cos{x} + i\sin{x}\right) 可以得到三角函数的另一个表达式

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

那么代入 f(x) 就有:

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

注意到此处是在 \mathbb{Z}_{998244353} 上做 NTT,那么相应地,虚数单位 i 应该换成 \sqrt{-1} \equiv \sqrt{998244352} \equiv 86583718 \pmod{998244353}
直接按式子求就完了。

啥?你问 \tan{f(x)} 怎么求?回去学高中数学必修四吧.webp