单位根反演

这东西就一个式子，但是能推出很多有意思的东西。

\[ [n\mid a]=\frac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{ai} \] 其中 $\mid$ 为整除符号，$w_n^i$ 为第 $i$ 个 $n$ 次单位根。

考虑证明：

当 $n\mid a$ 时，设 $a=kn$，则 \[ \begin{aligned} &\frac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{ai}\\ =&\frac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{nki}\\ =&\frac{1}{n}\sum\limits_{i=0}^{n-1}(w_n^n)^{ki}\\ =&\frac{1}{n}\sum\limits_{i=0}^{n-1}1\\ =&1 \end{aligned} \]

当 $n\nmid a$ 时，考虑等比数列求和 \[ \begin{aligned} &\frac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{ai}\\ =&\frac{1}{n}\frac{1-w_n^{an}}{1-w_n^a} \end{aligned} \] 注意到 $1-w_n^{an}=0$ 且 $1-w_n^a\not= 0$（这也是为啥 $n\mid a$ 时不能这么做，因为公比为 $1$ 了），所以原式为 $0$。

注意一下如果在模质数意义下有 $n$ 次单位根（即 $n\mid(p-1)$）那么这个式子也是成立的。

一个推导： \[ [a\equiv b\pmod n]=\frac{1}{n}\sum\limits_{i=0}^{n-1}w_n^{ai}w_n^{-bi} \]

另一个推导：如果我们有一个项数很多的多项式（设项数为 $n$），我们想求 $[x^t]f(x),[x^{k+t}]f(x),[x^{2k+t}]f(x),\dots$ 之和，且满足：

$k$ 较小
多项式的点值便于快速计算
如果是在模质数意义下，则应存在 $k$ 次单位根

我们可以通过单位根反演快速计算，具体如下： \[ \begin{aligned} &\sum\limits_{i=0}^{n-1}[i\equiv t\pmod k][x^i]f(x)\\ =&\frac{1}{k}\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{k-1}w_k^{(i-t)j}[x^i]f(x)\\ =&\frac{1}{k}\sum\limits_{j=0}^{k-1}w_k^{-tj}\sum\limits_{i=0}^{n-1}w_k^{ij}[x^i]f(x)\\ =&\frac{1}{k}\sum\limits_{j=0}^{k-1}w_k^{-tj}f(w_k^j) \end{aligned} \] 来一道例题

loj6485 LJJ 学二项式定理

输入以下变量的值：$ n, s , a_0 , a_1 , a_2 , a_3$，求以下式子的值： \[ \left[ \sum_{i=0}^n \left( {n\choose i} \cdot s^{i} \cdot a_{i\bmod 4} \right) \right] \bmod 998244353 \] 我们枚举 $a_0,a_1,a_2,a_3$ 前面的系数，则 \[ \begin{aligned} ans=&\sum\limits_{k=0}^3a_k\sum\limits_{i=0}^n[i\bmod4=k]\binom{n}{i}s^i\\ =&\sum\limits_{k=0}^3a_k\sum\limits_{i=0}^n[4\mid(i-k)]\binom{n}{i}s^i\\ =&\frac{1}{4}\sum\limits_{k=0}^3a_k\sum\limits_{i=0}^{n}\sum_{j=0}^{3}w_4^{j(i-k)}\binom{n}{i}s^i\\ =&\frac{1}{4}\sum\limits_{k=0}^3a_k\sum\limits_{i=0}^{n}\sum_{j=0}^{3}w_4^{ji}w_4^{-jk}\binom{n}{i}s^i\\ =&\frac{1}{4}\sum\limits_{k=0}^3a_k\sum_{j=0}^{3}w_4^{-jk}\sum\limits_{i=0}^{n}w_4^{ji}\binom{n}{i}s^i\\ =&\frac{1}{4}\sum\limits_{k=0}^3a_k\sum_{j=0}^{3}w_4^{-jk}(sw_t^j+1)^n \end{aligned} \] 然后在模 $998244353$ 意义下的 $4$ 次单位根为 $g^{\frac{p-1}{4}}$，其中 $g$ 是某个原根。直接快速幂就好了。

代码

用单位根反演证明 IDFT 正确性

证明 IDFT 那个方法本质就是单位根反演。 \[ \begin{aligned} f'[k]&=\sum\limits_{i=0}^nw_n^{-ki}F(w_n^i)\\ &=\sum\limits_{i=0}^{n-1}w_n^{-ki}\sum\limits_{j=0}^{n-1}f_jw_n^{ij}\\ &=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}f_jw_n^{(j-k)i}\\ &=\sum\limits_{j=0}^{n-1}f_j\sum\limits_{i=0}^{n-1}w_n^{(j-k)i}\\ &=n\sum\limits_{j=0}^{n-1}f_j[n\mid (j-k)]\\ &=nf_k \end{aligned} \]

Bluestein's Algorithm

有的时候我们单位根反演完了以后要对每个 $k$ 求形似 $\sum\limits_{i=0}^{n-1}w_n^{ik}f_i$ 的东西，而 $n$ 不一定是 $2$ 的次幂。暴力求是 $O(n^2)$ 的，有没有优化方法？

注意到这实际上是一个任意长度的 DFT，当 $n$ 是 $2$ 的次幂时就是普通的 FFT，而 $n$ 不是 $2$ 的次幂时不能直接 FFT，我们考虑对 $ik$ 做文章。

形式1： \[ ik=\frac{-(k-i)^2+i^2+k^2}{2} \] 所以有 \[ \begin{aligned} &\sum\limits_{i=0}^{n-1}w_n^{ik}f_i\\ =&\sum\limits_{i=0}^{n-1}w_n^{\frac{-(k-i)^2}{2}+\frac{i^2}{2}+\frac{k^2}{2}}f_i\\ =&w_n^{\frac{k^2}{2}}\sum\limits_{i=0}^{n-1}w_n^{\frac{-(k-i)^2}{2}}w_n^{\frac{i^2}{2}}f_i\\ =&w_{2n}^{k^2}\sum\limits_{i=0}^{n-1}w_{2n}^{-(k-i)^2}w_{2n}^{i^2}f_i\\ \end{aligned} \] 我们注意到求和号右面是一个卷积的形式，所以我们做一次正常的卷积就可以了。

有的时候我们是在模质数意义下做的，可能没有 $2n$ 次单位根，所以这个时候我们要利用到形式2： \[ ik=\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2} \] 所以有 \[ \begin{aligned} &\sum\limits_{i=0}^{n-1}w_n^{ik}f_i\\ =&\sum\limits_{i=0}^{n-1}w_n^{\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}}f_i\\ =&w_n^{-\binom{k}{2}}\sum\limits_{i=0}^{n-1}w_n^{\binom{i+k}{2}}w_n^{-\binom{i}{2}}f_i\\ =&w_n^{-\binom{k}{2}}\sum\limits_{i=0}^{n-1}w_n^{\binom{i+k}{2}}w_n^{-\binom{i}{2}}f_i\\ \end{aligned} \] 这样就可以避免不存在 $2n$ 次单位根的问题了。

这个东西可以用来做循环卷积，即 \[ c_k=\sum\limits_{i=0}^n\sum\limits_{j=0}^{n}[i+j\equiv k\pmod n]a_ib_j \] 然后是推式子时间 \[ \begin{aligned} c_k&=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}[i+j\equiv k\pmod n]a_ib_j\\ &=\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}[(i+j-k)\bmod n=0]a_ib_j\\ &=\frac{1}{n}\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}\sum\limits_{t=0}^{n-1}w_n^{t(i+j-k)}a_ib_j\\ &=\frac{1}{n}\sum\limits_{t=0}^{n-1}w_n^{-kt}\left(\sum\limits_{i=0}^{n-1}w_n^{it}a_i\right)\left(\sum\limits_{j=0}^{n-1}w_n^{jt}b_j\right) \end{aligned} \] 注意到两个括号内都是长度为 $n$ 的 DFT，所以对 $a$ 和 $b$ 做任意基 DFT，然后相乘就得到点值表示了，最后需要做长度为 $n$ 的 IDFT，和正着做类似。

顺便说一下关于 FFT 的本质，我们需要注意到如果我们把两个长为 $n$ 的数组都做一遍 DFT，然后对应位相乘再 IDFT 回去，这样得到的是两个数组做长度为 $n$ 的循环卷积。我们平时写的 FFT 也是长度为 $2^k$ 的循环卷积，只不过我们一开始已经补到了比最高次还要高的 $2^k$ 长度，所以不会出现循环。

给一道关于 FFT 本质的例题：「CTSC2010」性能优化，这篇写的比较辣鸡，建议看别人的。

再给一道比较难的单位根反演的例题：「HNOI2019」白兔之舞