套路

单位根滤波抽隔项

要 ∑k≡r (mod m)ak\sum_{k\equiv r\ (\mathrm{mod}\ m)}a_k，就把 f(x)=∑akxkf(x)=\sum a_kx^k 在 mm 次单位根 1,ω,…,ωm−11,\omega,\dots,\omega^{m-1} 上各取一次值再加权平均：1m∑jω−jrf(ωj)\dfrac1m\sum_{j}\omega^{-jr}f(\omega^{j}) 恰好只剩下标 ≡r\equiv r 的那些项。

解题套路

设 f(x)=∑kakxkf(x)=\sum_{k}a_kx^{k}，ω=cos⁡2πm+isin⁡2πm\omega=\cos\dfrac{2\pi}{m}+i\sin\dfrac{2\pi}{m} 是 mm 次单位根。则对每个 rr，

∑k≡r (mod m)ak=1m∑j=0m−1ω−jrf(ωj).\sum_{k\equiv r\ (\mathrm{mod}\ m)}a_k=\frac1m\sum_{j=0}^{m-1}\omega^{-jr}f(\omega^{j}).

m=2m=2 就是最熟的那一条：f(1)+f(−1)2\dfrac{f(1)+f(-1)}2 是偶次项和、f(1)−f(−1)2\dfrac{f(1)-f(-1)}2 是奇次项和。m=4m=4 时 ω=i\omega=i，四个取值点是 1,i,−1,−i1,i,-1,-i。

为什么成立

把右边的求和交换次序，aka_k 的系数是

1m∑j=0m−1ωj(k−r).\frac1m\sum_{j=0}^{m-1}\omega^{j(k-r)} .
  • 若 m∣k−rm\mid k-r，每一项都是 11，和为 mm，系数为 11；
  • 否则 ωk−r≠1\omega^{k-r}\neq1，这是公比不为 11 的等比和，等于 ωm(k−r)−1ωk−r−1=0\dfrac{\omega^{m(k-r)}-1}{\omega^{k-r}-1}=0。

于是只有下标 ≡r\equiv r 的 aka_k 活下来，别的全被抵消——「滤波」这个名字就是这个意思。

用在二项式上

取 f(x)=(1+x)nf(x)=(1+x)^{n}，ak=Cnka_k=\mathrm{C}_n^k，立刻得到「每隔 mm 个取一个二项系数」的和。m=4m=4 时四个点的值是 2n2^{n}、(1+i)n(1+i)^{n}、00、(1−i)n(1-i)^{n}——其中 (1+x)n(1+x)^n 在 x=−1x=-1 处取 00（n⩾1n\geqslant1），白送一项，所以真正要算的只有 (1±i)n(1\pm i)^{n}。

(1±i)n(1\pm i)^{n} 不必写成模与辐角的形式：(1+i)2=2i(1+i)^{2}=2i、(1+i)4=−4(1+i)^{4}=-4，四次一循环，指数除以 44 取余就能写出来；(1−i)n(1-i)^{n} 是它的共轭，实部同、虚部反。

注意

  • rr 要按题目问的那一组取，别与「第几项」混淆：问的是下标 kk 除以 mm 的余数。
  • 别漏掉 j=0j=0 那一项（就是 f(1)f(1)），它往往是主项。
  • 算完拿一个小的 nn 代进去验一遍——这一步几秒钟，能挡住 ω−jr\omega^{-jr} 的指数写反。

学它之前先会

共 3 条前置、最深 3 层。

出现在以下题目中

共 1 道题考到本条。