单位根
定义 $\mathbb{C}$ 上 $x^n=1$ 的 $n$ 个解为 $\omega _ {n}^{0} \sim \omega _ {n}^{n-1}$，其中 $\omega _ {n}^{1}=e^{\frac{2 \pi i}{n}}$
在模 $P$ 意义下，设 $g$ 为 $P$ 的原根，则 $\omega _ {n}^{1}=g^{\frac{P-1}{n}}$
单位根反演
对于 $[n | k]$，有：
$$
[n|k]=\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{pk}
$$
证明
若 $k=nt$，则：
$$
\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{pk}=\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{(pnt) \bmod n}=\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{0}=1
$$
若 $n \not| k$，则：
$$
\frac{1}{n}\sum _ {p=0}^{n-1}\omega _ {n}^{pk}=\omega _ {n}^{0}\frac{1-\omega _ {n}^{kn}}{n(1-\omega _ {n}^{k})}=\omega _ {n}^{0}\frac{1-\omega _ {n}^{0}}{n(1-\omega _ {n}^{k})}=0
$$
应用
对于多项式 $f(x)=\sum _ {p=0}^{N-1}a _ px^p$，若要求 $g(n)=\sum _ {p=0}^{N-1}a _ p[n|p]$，则有：
$$
\begin{aligned}
\frac{\sum _ {p=0}^{n-1}f(\omega _ {n}^{p})}{n}
=& \frac{\sum _ {p=0}^{n-1}\sum _ {q=0}^{N-1}a _ q\omega _ {n}^{pq}}{n} \\
=& \sum _ {q=0}^{N-1}a _ q\frac{\left(\sum _ {p=0}^{n-1}\omega _ {n}^{pq}\right)}{n} \\
=& \sum _ {q=0}^{N-1}a _ q [n|q] \\
\end{aligned}
$$
数列合并
例 1
若有序列 ${a _ n},{b _ n}$，构造序列 ${p _ n}$ 满足：
$$
p _ {n}=\begin{cases}{a _ {n}} & {\mathrm{n \equiv 1 \pmod {2}}} \\ {b _ {n}} & {\mathrm{n \equiv 0 \pmod{2}}}\end{cases}
$$
通过单位根的性质，也可以写作：
$$
p _ {n}=\frac{1}{2}\left(\cos(\pi n)\left(b _ {n}-a _ {n}\right)+a _ {n}+b _ {n}\right)
$$
例 2
若有函数 $f(n)$ 满足：
$$
f(n)=\begin{cases}{\frac{n}{2}} & {n \equiv 0 \pmod{2}} \\ {3 n+1} & {n \equiv 1 \pmod{2}}\end{cases}
$$
则也可以写为：
$$
f(n)=\frac{1}{4}(2+7 n-\cos (\pi n)(2+5 n))
$$
例 3
若有序列 ${p _ n}$ 满足：
$$
p _ {n}=\begin{cases}{a _ {n}} & {\mathrm{n \equiv 0 \pmod{3}}} \\ {b _ {n}} & {\mathrm{n \equiv 1 \pmod{3}}} \\ {c _ {n}} & {\mathrm{n \equiv 2 \pmod{3}}}\end{cases}
$$
则也可以写为：
$$
p _ {n}=\frac{1}{3}\left(\cos \left(\frac{2 \pi n}{3}\right)\left(2 a _ {n}-b _ {n}-c _ {n}\right)+a _ {n}+\sqrt{3} \sin \left(\frac{2 \pi n}{3}\right)\left(b _ {n}-c _ {n}\right)+b _ {n}+c _ {n}\right)
$$
