单位根反演入门

单位根（unit root）：$k$次单位根记做$\omega_k=e^{\frac{2\pi i}{k}}$。

单位根反演

如同大多数反演一样，单位根反演（unit root inversion）也是基于一个恒等式：

$$[d|n]=\frac{1}{d}\sum_{i=0}^{d-1}\omega_d^{ni}$$

证明

若$d|n$，则上式显然等于$1$。

否则，根据等比数列求和公式可以得到

$$\sum_{i=0}^{d-1}\omega_d^{ni}=\frac{1-\omega_d^{dn}}{1-\omega_d^n}=0$$

证毕。

数论中的单位根

上午中的单位根需要满足什么性质吗？$k$次单位根需要满足，$\omega_k^i\ne 1$（$1<i<k$），$\omega_k^k=1$。并不需要其他的条件。因此如果你担心浮点数运算的速度和精度问题，可以考虑在模$P$意义下找到$k$次单位根——也就是阶为$k$的数。

生成函数与单位根反演

考虑一个 OGF$F(x)=\sum_{i=0}^n a_ix^i$。我们想求所有指数是$k$的倍数的项的系数和，也就是$\sum_{i=0}^n a_i[k|i]$。单位根反演一波得到

$$\begin{aligned} &\sum_{i=0}^n a_i[k|i]\\ =&\sum_{i=0}^na_i\frac{1}{k}\sum_{j=0}^{k-1}\omega_{k}^{ij}\\ =&\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^na_i\left(\omega_{k}^{j}\right)^i\\ =&\frac{1}{k}\sum_{j=0}^{k-1}F(\omega_k^j) \end{aligned}$$

那么只要我们能快速计算$F$函数的点值，就可以快速计算上述的系数和。

LJJ 学二项式定理

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

$$\sum_{i=0}^n\binom{n}{i}s^ia_{i\bmod 4}\pmod {998244353}$$

$n\le 10^{18},s,a_0,a_1,a_2,a_3\le 10^8$。

构造 OGF$F(x)=\sum_{i=0}^n\binom{n}{i}s^ix^i$。那么我们只需要知道下标$\bmod4$的四种余数的系数和，就可以求出答案了。

对于$i\bmod 4=0$，即$4|i$，我们可以直接反演。如果余数非零，那么我们可以给$F(x)$乘$x^t$来右移$t$位，然后也可以反演。因此接下来的问题是：

• 单位根$\omega_4$是多少。
• $F$的点值如何快速计算。

由于模数特殊，容易发现$\omega_4=3^{\frac{P-1}{4}}\bmod 998244353$。

根据二项式定义，容易得到$F(x)=(sx+1)^n$。

因此时间复杂度$O(\log_2n)$。

代码

PYXFIB

给定$n,k,p$，求

$$\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor}\binom{n}{ik}F_{ik}\pmod {p}$$

其中$F$是斐波那契数列，$F_0=F_1=1,F_i=F_{i-1}+F_{i-2}$。

$n\le 10^{18},k\le 20000,p\le 10^9,p\bmod k=1$，$p$是质数。

容易发现我们要求是

$$\sum_{i=0}^{n}\binom{n}{i}F_{i}[k|i]$$

到这里有两种算法。

算法一

单位根反演的结论在矩阵意义上也是成立的。设$M^i$表示$F_i$对应的矩阵。因此我们要求是

$$\sum_{i=0}^{n}\binom{n}{i}M^i[k|i]$$

那么构造 OGF$F(x)=\sum_{i=0}^n\binom{n}{i}M^ix^i=(Mx+I)^n$。由于$p$是质数且$p\bmod k=1$，因此我们找到$p$的一个原根$g$，就可以得到$\omega_k=g^{\frac{p-1}{k}}$。这样就可以单位根反演了。

时间复杂度$O(k\log_2n)$。

算法二

其实斐波那契数列本身就可以表示成等比数列的和的形式。使用特征根或者生成函数法可以得到

$$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}$$

那么我们求两次即可。单位根还是按照算法一的方式求出。使用类似的方法构造生成函数。

然后还是对$\sqrt{5}$扩域再计算。

时间复杂度$O(k\log_2n)$。