单位根反演

引子

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

$$\sum _ {i=0}^{n} {n \choose 2i}$$

不妨构造二项式

$$(1+x)^n=\sum _ {i=0}^{n} {n \choose i} x^i$$

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

$$\begin {align} 2^n &= \sum _ {i=0}^{n} {n \choose i} \\ 0 &= \sum _ {i=0}^{n} (-1)^i {n \choose i} \end {align}$$

两式相加，则有

$$2^n=2*\sum _ {i=0}^{\lfloor \frac{n}{2} \rfloor} {n \choose 2i}$$

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

那如果我们现在想计算

$$\sum _ {i=0} ^{n} {n \choose ki}$$

该怎么办？

简介

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

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

形式化的，我们可以求

$$\sum _ {i=0}^{\lfloor \frac{n}{k} \rfloor} [x^{ik}] f(x)$$

知识储备

单位根

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

单位根在复平面上的分布将单位圆均分为$n$份，在第一象限的最靠近实轴的单位根记为$\omega n^1$，一般也可记为$\omega {n}$。其余的按逆时针排序，分别为$\omega _ n^{2 \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$的本原单位根。

性质：

$$\forall k,[n \mid k]=\frac{1}{n}\sum _ {i=0}^{n-1} \omega _ {n}^{ik}$$

证明：

若$n \mid k$，则有

$$Ans=\frac{1}{n} \sum _ {i=0}^{n-1} \omega _ {n}^{ink'}=\frac{1}{n}\sum _ {i=0}^{n-1} 1=1$$

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

$$Ans=\frac{1}{n} \frac{\omega _ {n}^{0}-\omega _ {n}^{nk}}{1-\omega _ {n}^{k}}=0$$

得证。

应用

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

$$\sum _ {i=0} ^{n} {n \choose ki}$$

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

$$f(x)=\sum _ {i=0}^{N} {N \choose i} x^i$$

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

我们不妨设

$$f(x)=\sum _ {i=0}^{N} a _ i x^i<$$

那我们只需要求

$$\begin {align} Ans &= \sum _ {i=0}^{N} ([x^i]f(x)) [k \mid i] \\ &= \sum _ {i=0}^{N} ([x^i]f(x)) \frac{1}{k} \sum _ {j=0}^{k-1} \omega _ {k}^{ij} \\ &= \sum _ {i=0}^{N} ([x^i]f(x)) \frac{1}{k}\sum _ {j=0}^{k-1} (\omega _ {k}^{j})^i \\ &= \sum _ {i=0}^{N} a _ i \sum _ {j=0}^{k-1} (\omega _ {k}^{j})^i\\ &= \sum _ {j=0}^{k-1} \sum _ {i=0}^{N} (\omega _ {k}^{j})^i\\ &= \frac{1}{k}\sum _ {j=0}^{k-1} f(\omega _ {k}^{j}) \end{align}$$

即可。

同时注意到

$$f(x)=(x+1)^n$$

例题

[LOJ 6485] LJJ 学二项式定理

Link

题意

给定$n,s,a 0,a 1,a 2,a 3$，求

$$[\sum _ {i=0}^{n} ({n \choose i} s^i a _ {i \bmod4}) ] \bmod 998244353$$

题解

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

$$\begin {align} f(x) &= \sum _ {i=0}^{n} {n \choose i} s^i x^i *1^{n-i} \\ &= (sx+1)^n \end {align}$$

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

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

第二种构造方法：

$$\begin {align} f(x) &= \sum _ {i=0}^{n} {n \choose n-i} s^{n-i} x^i \\ f(x) &=(s+x)^n \end {align}$$

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