# litlocus 题解导出

导出时间：2026/10/22 02:34:25

---

## 单位根反演的简单应用

- 原题：Super EZ Problem 1.3
- 作者：GF1048576
- 审核时间：2026/10/21 15:15:27

取 $\omega=e^{2\pi i/p}$, 对问题施单位根反演, 答案为
$$
N=\frac1p\sum_{j=0}^{p-1}[x^p]\prod_{a=1}^{2p}(1+x\omega^{ja}).
$$
在 $1,2,\dots,2p$ 中, 模 $p$ 的每个剩余类都恰好出现两次. 因此, 当 $j\neq 0$ 时, 
$$
\prod_{a=1}^{2p}(1+x\omega^{ja})
=\left(\prod_{r=0}^{p-1}(1+x\omega^r)\right)^2.
$$
又因为 $p$ 为奇质数, 有 $\prod_{r=0}^{p-1}(1+x\omega^r)=1+x^p$, 因此
$$
[x^p]\prod_{a=1}^{2p}(1+x\omega^{ja})=[x^p](1+x^p)^2.
$$
$j=0$ 的情况平凡, 整理后可得答案为 $\frac1p\left(\binom{2p}{p}+2(p-1)\right)$.