概念

单位根反演，顾名思义是基于单位根性质的反演，用于处理和取模有关的问题，或者在有关 FFT 的题目中进行特殊的构造（虽然还没做过）。

通常用单位根在模意义下的替代品原根。

反正没见过的模数原根统一猜 3

思路

性质：\([n \mid a] = \frac{1}{n} \sum\limits_{k = 0}^{n - 1} w_n^{ak}\).

导出单位根反演：\([a \equiv b \pmod n] = [a - b \equiv 0 \pmod n] = \frac{1}{n} \sum\limits_{k = 0}^{n - 1} w_n^{(a - b) k} = \frac{1}{n} \sum\limits_{k = 0}^{n - 1} w_n^{ak} w_n^{-bk}\).

通常当模数较小时可以考虑枚举余数，然后套上单位根反演。

例题：LOJ #6485. LJJ 学二项式定理

求 \(\sum\limits_{i = 0}^n {n \choose i} s^i a_{i \bmod 4}\).

考虑枚举 \(i \bmod 4\) 的余数，化简得 \(\sum\limits_{i = 0}^n {n \choose i} s^i \sum\limits_{j = 0}^{3} [i \equiv j \pmod 4] a_j\).

根据单位根反演可知 \(\sum\limits_{i = 0}^n {n \choose i} s^i \frac{1}{4} \sum\limits_{j = 0}^3 a_j \sum\limits_{k = 0}^{3} w_4^{(i - j) k}\).

拆开单位根得到 \(\sum\limits_{i = 0}^n {n \choose i} s^i \frac{1}{4} \sum\limits_{j = 0}^3 a_j \sum\limits_{k = 0}^{3} w_4^{ik} w_4^{-jk}\).

交换求和顺序再整理得 \(\frac{1}{4} \sum\limits_{j = 0}^3 a_j \sum\limits_{k = 0}^3 w_4^{-jk} \sum\limits_{i = 0}^n {n \choose i} s^i\).

后面的和式可以二项式定理得 \(\frac{1}{4} \sum\limits_{j = 0}^3 a_j \sum\limits_{k = 0}^3 w_4^{-jk} (s w_4^k + 1)^n\).