（也许是）冷门算法——单位根反演

~~（由于太懒不一定）~~同步于[我的博客](https://czyhe.me/algorithm/unit-root-inv/unit-root-inv/) # 前置技能 - [单位根](https://zhang-rq.github.io/2018/08/13/%E5%8D%95%E4%BD%8D%E6%A0%B9%E5%8F%8D%E6%BC%94/#%E5%8D%95%E4%BD%8D%E6%A0%B9) - [二项式定理](https://baike.baidu.com/item/二项式定理) - [组合数](https://baike.baidu.com/item/组合数) # 引入 从[一道题](https://loj.ac/problem/6485)说起…… > 给定$n,s,a_0,a_1,a_2,a_3$，求 > > $$\sum_{i=0}^{n} {n \choose i} s^i a_{i \bmod 4}$$ > > 答案对$998244353$取模 > > $1 \le n \le 10^{18}, 1 \le s,a_0,a_1,a_2,a_3 \le 10^8$ ~~一脸绝望~~ 在高中的时候，数学老师教会了我们$(a+b)^{n}=\sum_{i=0}^{n}{n \choose i}a^{i}b^{n-i}$，然后惊喜的发现这道题不能这么做！ 在$OI$中，我们学习了单位根的基本性质（如果还未学，可从**前置技能**部分的**单位根**处点击链接学习），关于单位根还有一个迷之用法——单位根反演 # 构造生成函数 对于数列$a_i$，构造其生成函数$f(x)=\sum_{i=0}^{n}a_ix^i$ 现在我们想知道所有下标是$k$的倍数的$a_i$的和，既$\sum_{i=0}^{n}a_i[k|i]$ # 一个关于$[n|k]$的等式 有一个关于$n$次单位根$w_n$的等式，看起来十分有趣 ~~毒瘤~~ $$[n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki}$$ ## 证明 如果$n \mid k$，设$k=np$，则 $$\frac{1}{n}\sum_{i=0}^{n-1}w_n^{npi \bmod n}=\frac{1}{n}\sum_{i=0}^{n-1}w_n^{0}=1$$ 注：$npi \bmod n=(n \bmod n) \times (pi \bmod n)=0 \times (pi \bmod n)=0$ 如果$n \nmid k$，根据等比数列求和公式，则 $$\frac{1}{n}\sum_{i=0}^{n-1}\omega_{n}^{ki}=\frac{1}{n}(w_n^{0}\frac{1-\omega_n^{k(n-1)}}{1-w_n^{k}})=\frac{w_n^0-w_n^{kn}}{n(1-\omega_n^{k})}=0$$ 于是对于$N$次单位根$w_N$可以这么搞： $$\frac{\sum_{i=0}^{N-1}f(w_N^i)}{N}=\frac{\sum_{i=0}^{n}a_i\sum_{j=0}^{N-1}w_N^{ij}}{N}=\sum_{i=0}^{n}a_i[N \mid i]$$ 于是就可以得到所有下标是$N$的倍数的$a_i$的和了 # 有一个问题 但是发现，只知道所有$N \mid i$的$a_i$的和还不够有用，如果分别知道$i \bmod N \in [0,N-1]$的$a_i$的和的话就十分有用了 数学老师告诉我们，$f(x)$通过乘以$x$的若干次幂可以实现函数的平移（虽然说这句话不太严谨……但还是可以凑合着看看……） 比如说现在有$f(x)=a_0x^{0}+a_1x^{1}+a_2x^{2} + \dots$ 对其乘上$x^{-1}$后会得到$f(x)x^{-1}=a_0x^{-1}+a_1x^{0}+a_2x^{1} + \dots$ 再用上面的方法求后就得到了$N \bmod i = 1$的所有$a_i$和 # 回到例题 在这道题中，构造$f(x)=\sum_{i=0}^{n} {n \choose i} s^i x^i 1^{n-i}=(sx+1)^n$ 则答案为$\sum_{i=0}^{3}a_ic_i$，其中$c_i=\sum\limits_{j=0}^{n}{n \choose j}s^j[j \bmod 4 = i]$ 对于$c_i$的$f(\omega_N^j)$，因为需要将$\omega_N^{j}$向右平移$i$次，只需要将其变为$\huge \frac{f(\omega_N^j)}{\omega_N^{ij \bmod 4}}$即可 # 扩展到矩阵上 [bzoj 3328](https://www.lydsy.com/JudgeOnline/problem.php?id=3328) ## 题目描述 给定$n,k,p$，求 $$\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} {n \choose ik}F_{ik}$$ 其中$F_0=F_1=1$，且$\forall n \ge 2,F_i=F_{i-1}+F_{i-2}$ 答案对$p$取模 $1 \le n \le 10^{18}$ $1 \le k \le 20000$ $1 \le p \le 10^9$ $p$是素数 $p \bmod k = 1$ ## 题解 单位根反演的结论在矩阵意义上也是成立的 也就是说求 $$\sum_{i=0}^{n} {n \choose i} F_i [k \mid i]$$ 设$A$是斐波那契数列的转移矩阵，$I$为单位矩阵 通过套用二项式定理，有 $$f(x)=(Ax+I)^n=\sum_{i=0}^{n} {n \choose i}A^ix^iI^{n-i}$$ 再套用单位根反演，有 $$T=\frac{\sum_{i=0}^{k-1}f(\omega_k^i)}{k}$$ 然后就做完了，答案就是矩阵$T$的左上角 # 总结 如果想计算序列$a_0, a_1,a_2, \dots , a_n$的所有满足$k|i$的$a_i$的和的话 首先构造$f(x)=\sum_{i=0}^{n}a_ix^i$ 然后将$\omega_k^i(i \in [0,k-1])$依次代入到$f(x)$中，并求和 最后除以$k$即可 也就是说 $$\sum_{i=0}^{n}a_i[k|i]=\frac{1}{k}\sum_{i=0}^{k-1}f(\omega_k^i)$$ # 参考文献 [Zhang-RQ 单位根反演学习笔记](https://zhang-rq.github.io/2018/08/13/%E5%8D%95%E4%BD%8D%E6%A0%B9%E5%8F%8D%E6%BC%94/) [shadowice1984 loj6485 LJJ学二项式定理](https://www.luogu.org/blog/ShadowassIIXVIIIIV/loj6485-ljj-xue-er-xiang-shi-ding-li) [DT_Kang 【4.13 提高班小记】单位根&&杂题](https://blog.csdn.net/DT_Kang/article/details/79944113) [Mys_C_K [真学习笔记] 前夕 - 单位根反演 - 广义容斥](https://blog.csdn.net/Mys_C_K/article/details/81388266) [Regina8023 【BZOJ 3328】PYXFIB](https://blog.csdn.net/regina8023/article/details/45007551)