式子：
\[[n \mid d] = \frac{1}{n} \sum\limits_{i = 0}^{n - 1} \omega_n^{id}
\]
最常见的应用是 \([x \equiv y \pmod n] = [n \mid (x - y)] = \sum\limits_{i = 0}^{n - 1} \omega_n^{(x - y)i}\)。
1. LOJ6485 LJJ 学二项式定理
单位根反演入门题。
\[\sum\limits_{i = 0}^n \binom{n}{i} m^i a_{i \bmod 4}
\]
\[= \sum\limits_{i = 0}^n \binom{n}{i} m^i \sum\limits_{j = 0}^3 [4 \mid (i - j)] a_j
\]
\[= \frac{1}{4} \sum\limits_{i = 0}^n \binom{n}{i} m^i \sum\limits_{j = 0}^3 a_j \sum\limits_{k = 0}^3 \omega_4^{(i - j)k}
\]
\[= \frac{1}{4} \sum\limits_{j = 0}^3 a_j \sum\limits_{k = 0}^3 \omega_4^{-jk} \sum\limits_{i = 0}^n \omega_4^{ik} m^i
\]
\[= \frac{1}{4} \sum\limits_{j = 0}^3 a_j \sum\limits_{k = 0}^3 \omega_4^{-jk} (m \omega_4^k + 1)^n
\]
我们知道在模 \(998244353\) 意义下 \(\omega_4 = g^{\left\lfloor\frac{mod - 1}{4}\right\rfloor}\)，其中 \(g\) 为 \(998244353\) 的原根。这样就可以算了。