Unit_Root_Inversion

结论：

$$[ n \mid a ] = \dfrac { 1 } { n } \sum _ { i = 0 } ^ { n - 1 } \omega _ {n} ^ {ai}$$

证明略，分 $ n \mid a $ 和 $ n \nmid a $ 讨论一下就好了。

其他形式：

$$
\begin{aligned}
[ a \equiv b \pmod{n} ] = [ a - b \equiv 0 \pmod {n} ] = \dfrac{1}{n} \sum _ { i = 0 } ^ { n - 1 } \omega _ {n} ^ { ( a - b ) i}
\end{aligned}
$$

一般不会使用复数单位根的形式，而是使用原根来实现具体计算。

例题一：LOJ6485 LJJ 学二项式定理

• 一般的推导即可
• 二项式定理

---

例题二：P5591 小猪佩奇学数学

• 反演后做 Whk 数列题

---

例题三：UOJ408 复读机

• 涉及到一点 EGF
• 反演只有最开始的一步

---

据说还有 Bluestein 算法。

咕了。