「算法笔记」多项式三角函数

使用欧拉公式可以轻松求出多项式三角函数。


概述

给定一个 $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);
}

发表评论