专栏文章

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

nnekko
算法·理论参与者 26已保存评论 27

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
27 条
当前快照
1 份
快照标识符
@mhz5sq1t
此快照首次捕获于
2025/11/15 01:56
4 个月前
此快照最后确认于
2025/11/29 05:24
3 个月前
查看原文
~~（由于太懒不一定）~~同步于我的博客

前置技能

引入

从一道题说起……
给定n,s,a0,a1,a2,a3n,s,a_0,a_1,a_2,a_3，求
∑i=0n(ni)siai mod 4\sum_{i=0}^{n} {n \choose i} s^i a_{i \bmod 4}
答案对998244353998244353取模
1≤n≤1018,1≤s,a0,a1,a2,a3≤1081 \le n \le 10^{18}, 1 \le s,a_0,a_1,a_2,a_3 \le 10^8
一脸绝望
在高中的时候，数学老师教会了我们(a+b)n=∑i=0n(ni)aibn−i(a+b)^{n}=\sum_{i=0}^{n}{n \choose i}a^{i}b^{n-i}，然后惊喜的发现这道题不能这么做！
在OIOI中，我们学习了单位根的基本性质（如果还未学，可从前置技能部分的单位根处点击链接学习），关于单位根还有一个迷之用法——单位根反演

构造生成函数

对于数列aia_i，构造其生成函数f(x)=∑i=0naixif(x)=\sum_{i=0}^{n}a_ix^i
现在我们想知道所有下标是kk的倍数的aia_i的和，既∑i=0nai[k∣i]\sum_{i=0}^{n}a_i[k|i]

一个关于[n∣k][n|k]的等式

有一个关于nn次单位根wnw_n的等式，看起来十分有趣 毒瘤
[n∣k]=1n∑i=0n−1ωnki[n|k]=\frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki}

证明

如果n∣kn \mid k，设k=npk=np，则
1n∑i=0n−1wnnpi mod n=1n∑i=0n−1wn0=1\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 mod n=(n mod n)×(pi mod n)=0×(pi mod n)=0npi \bmod n=(n \bmod n) \times (pi \bmod n)=0 \times (pi \bmod n)=0
如果n∤kn \nmid k，根据等比数列求和公式，则
1n∑i=0n−1ωnki=1n(wn01−ωnk(n−1)1−wnk)=wn0−wnknn(1−ωnk)=0\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
于是对于NN次单位根wNw_N可以这么搞：
∑i=0N−1f(wNi)N=∑i=0nai∑j=0N−1wNijN=∑i=0nai[N∣i]\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]
于是就可以得到所有下标是NN的倍数的aia_i的和了

有一个问题

但是发现，只知道所有N∣iN \mid i的aia_i的和还不够有用，如果分别知道i mod N∈[0,N−1]i \bmod N \in [0,N-1]的aia_i的和的话就十分有用了
数学老师告诉我们，f(x)f(x)通过乘以xx的若干次幂可以实现函数的平移（虽然说这句话不太严谨……但还是可以凑合着看看……）
比如说现在有f(x)=a0x0+a1x1+a2x2+…f(x)=a_0x^{0}+a_1x^{1}+a_2x^{2} + \dots
对其乘上x−1x^{-1}后会得到f(x)x−1=a0x−1+a1x0+a2x1+…f(x)x^{-1}=a_0x^{-1}+a_1x^{0}+a_2x^{1} + \dots
再用上面的方法求后就得到了N mod i=1N \bmod i = 1的所有aia_i和

回到例题

在这道题中，构造f(x)=∑i=0n(ni)sixi1n−i=(sx+1)nf(x)=\sum_{i=0}^{n} {n \choose i} s^i x^i 1^{n-i}=(sx+1)^n
则答案为∑i=03aici\sum_{i=0}^{3}a_ic_i，其中ci=∑j=0n(nj)sj[j mod 4=i]c_i=\sum\limits_{j=0}^{n}{n \choose j}s^j[j \bmod 4 = i]
对于cic_i的f(ωNj)f(\omega_N^j)，因为需要将ωNj\omega_N^{j}向右平移ii次，只需要将其变为f(ωNj)ωNij mod 4\huge \frac{f(\omega_N^j)}{\omega_N^{ij \bmod 4}}即可

扩展到矩阵上

bzoj 3328

题目描述

给定n,k,pn,k,p，求
∑i=0⌊nk⌋(nik)Fik\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} {n \choose ik}F_{ik}
其中F0=F1=1F_0=F_1=1，且∀n≥2,Fi=Fi−1+Fi−2\forall n \ge 2,F_i=F_{i-1}+F_{i-2}
答案对pp取模
1≤n≤10181 \le n \le 10^{18}
1≤k≤200001 \le k \le 20000
1≤p≤1091 \le p \le 10^9
pp是素数
p mod k=1p \bmod k = 1

题解

单位根反演的结论在矩阵意义上也是成立的
也就是说求
∑i=0n(ni)Fi[k∣i]\sum_{i=0}^{n} {n \choose i} F_i [k \mid i]
设AA是斐波那契数列的转移矩阵，II为单位矩阵
通过套用二项式定理，有
f(x)=(Ax+I)n=∑i=0n(ni)AixiIn−if(x)=(Ax+I)^n=\sum_{i=0}^{n} {n \choose i}A^ix^iI^{n-i}
再套用单位根反演，有
T=∑i=0k−1f(ωki)kT=\frac{\sum_{i=0}^{k-1}f(\omega_k^i)}{k}
然后就做完了，答案就是矩阵TT的左上角

总结

如果想计算序列a0,a1,a2,…,ana_0, a_1,a_2, \dots , a_n的所有满足k∣ik|i的aia_i的和的话
首先构造f(x)=∑i=0naixif(x)=\sum_{i=0}^{n}a_ix^i
然后将ωki(i∈[0,k−1])\omega_k^i(i \in [0,k-1])依次代入到f(x)f(x)中，并求和
最后除以kk即可
也就是说
∑i=0nai[k∣i]=1k∑i=0k−1f(ωki)\sum_{i=0}^{n}a_i[k|i]=\frac{1}{k}\sum_{i=0}^{k-1}f(\omega_k^i)

参考文献

Zhang-RQ 单位根反演学习笔记
shadowice1984 loj6485 LJJ学二项式定理
DT_Kang 【4.13 提高班小记】单位根&&杂题
Mys_C_K [真学习笔记] 前夕 - 单位根反演 - 广义容斥
Regina8023 【BZOJ 3328】PYXFIB

评论

共 27 条评论，欢迎与作者交流。

正在加载评论...