单位根反演

引子

假设现在我们要求一个式子

不妨构造二项式

我们现在将$x=1$,$x=-1$ 带入,则有

两式相加,则有

问题已经解决,$Ans=2^{2*n-1}$。

那如果我们现在想计算

该怎么办?

简介

单位根反演就是做以上工作的东西。

简而言之,如果能快速求出某个多项式的点值,那我们就可能能求出$x$的特定倍数幂的系数和。

形式化的,我们可以求

知识储备

单位根

根据$FFT$的前置知识,我们可以知道,对于一个$n$,若有$x^n-1=0$,则称$x$是$n$次单位根,记为$\omega_n$。

单位根在复平面上的分布将单位圆均分为$n$份,在第一象限的最靠近实轴的单位根记为$\omega_n^1$,一般也可记为$\omega_{n}$。其余的按逆时针排序,分别为$\omega_n^{1 \cdots n-1}$

所以我们不难发现如下几个性质:

  1. $ \omega_n^i +\omega_n^{i+n/2} (2|n)$

  2. $\omega_n^i=\omega_n^{i \% n}$

  3. $\omega_{kn}^{ki}=\omega_{n}^{i}$

由于性质3的存在,我们可以定义本原单位根。

本原单位根的定义是:若$\omega,n$满足$\omega^n-1=0$,且$n$是最小满足条件的,则称$\omega$是$n$的本原单位根。

我们不难发现,对于单位根$\omega_{n}^{i}$,若$\gcd(n,i)==1$,则$\omega_n^i$一定是n的本原单位根。

否则,设$d=\gcd(i,n)$,则$\omega_{n}^{i}=\omega_{n’d}^{i’d}=\omega_{n’}^{i’}$,$(\omega_{n’}^{i’})^{n’}-1=0$。并不是$n$的本原单位根。

性质:

证明:

若$n \mid k$,则有

否则,这玩意是个等比数列求和,根据高中知识,我们有

得证。

应用

现在我们考虑一开始提出的那个问题,求

这个就相当于在求(设$N=nk$)

的次数为$k$的倍数的项的系数和。

我们不妨设

那我们只需要求

即可。

同时注意到

例题

[LOJ 6485] LJJ 学二项式定理

Link

题意

给定$n,s,a_0,a_1,a_2,a_3$,求

题解

我们不妨不关注$a$数组部分,先构造二项式

现在只要分别求出$f(x)$除$4$余$0 \cdots 3$的系数之和即可,直接套用之前所讲的方法即可。

需要注意,在模$P$意义下,设$g$为$P$的原根,则$\omega_{n}^{1}=g^{\frac{P-1}{n}}$。

第二种构造方法:

注意,这里使用了$n-i$替换了$i$,所以要处理一下$a$数组的下标。