A SOLUTION FROM THE ARCHIVE单位根反演的简单应用GGF1048576审核通过2026/10/21原题 · Super EZ Problem 1.3 ↗导出这篇题解 .md取 ω=e2πi/p\omega=e^{2\pi i/p}ω=e2πi/p, 对问题施单位根反演, 答案为 N=1p∑j=0p−1[xp]∏a=12p(1+xωja).N=\frac1p\sum_{j=0}^{p-1}[x^p]\prod_{a=1}^{2p}(1+x\omega^{ja}).N=p1j=0∑p−1[xp] 在 1,2,…,2p1,2,\dots,2p1,2,…,2p 中, 模 ppp 的每个剩余类都恰好出现两次. 因此, 当 j≠0j\neq 0j=0 时, ∏a=12p(1+xωja)=(∏r=0p−1(1+xωr))2.\prod_{a=1}^{2p}(1+x\omega^{ja}) =\left(\prod_{r=0}^{p-1}(1+x\omega^r)\right)^2.a=1∏2p(1+xω 又因为 ppp 为奇质数, 有 ∏r=0p−1(1+xωr)=1+xp\prod_{r=0}^{p-1}(1+x\omega^r)=1+x^p∏r=0p−1(1+xω, 因此 [xp]∏a=12p(1+xωja)=[xp](1+xp)2.[x^p]\prod_{a=1}^{2p}(1+x\omega^{ja})=[x^p](1+x^p)^2.[xp]a=1∏2p j=0j=0j=0 的情况平凡, 整理后可得答案为 1p((2pp)+2(p−1))\frac1p\left(\binom{2p}{p}+2(p-1)\right)p1(.□