单位根反演备忘录

之前 Picks 来讲课,结果 Guideposts 那题被 boshi 秒了 boshi讲完我还在下面懵逼
后来去学了单位根反演

单位根反演

具体来说,就是将 $[n\mid k]$ 转化为一个容易化简,求值,带入的式子
$$ [n\mid k] = \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} $$

证明

  1. 当 $n\mid k$ 时,设 $k=t\cdot n$ ,则
    $$ \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} = \frac{\sum_{i=0}^{n-1}\omega_n^{n\cdot(ti)}}{n} =1=[n\mid k]$$
  2. 当 $n\nmid k$ 时,设
    $$ S=\sum_{i=0}^{n-1}\omega_n^{ki}\tag{1}$$

    $$\omega_n^k S = \sum_{i=1}^{n}\omega_n^{ki} \tag{2}$$
    将 $(1)-(2)$
    $$ (1-\omega_n^k)S = \omega_n^0-\omega_n^{kn} $$
    $$ S = \frac{\omega_n^0-(\omega_n^n)^k}{1-\omega_n^k} =0$$
    此时
    $$ \frac{1}{n}\sum_{i=0}^{n-1}\omega_n^{ki} = \frac{1}{n} \cdot S = 0 = [n\mid k] $$
    证毕

例题

看上去单位根反演没什么用处,但是实际上有很多式子可以使用它化简,这里讲几个例题

BZOJ3228 PYXFIB

题意

设 $F_i$ 为斐波那契数列的第 $i$ 项,给定 $n,k,p$ ,求
$$\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor} {n\choose {ik}} F_{ik} $$

思路

首先可以将式子转化成
$$\sum_{i=0}^{n}{n\choose i}\cdot F_i\cdot [k\mid i] $$
可以将 $F_i$ 用矩阵 $G^i$ 表示,其中
$$
G=
\begin{bmatrix}
0 & 1 \\
1 & 1
\end{bmatrix}
$$
于是转为求
$$ \sum_{i=0}^{n}{n\choose i} * G^i[k\mid i]$$
此时可以愉快的使用单位根反演
$$
\begin{eqnarray}
&&\sum_{i=0}^{n}{n\choose i} * G^i(\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{ij}) \\
&=&\frac{1}{k}\sum_{i=0}^{n}{n\choose i} * G^i\sum_{j=0}^{k-1}\omega_k^{ij} \\
&=&\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^n {n\choose i} * (G * \omega_k^j)^i \\
&=&\frac{1}{k}\sum_{j=0}^{k-1}(G * \omega_k^j+I)^n
\end{eqnarray}
$$
其中 $I$ 为单位矩阵,最后一步使用二项式定理转换来
于是求出关于 $P$ 的原根 $g$,将单位根 $\omega_k^i=g^{\frac{P-1}{k}i}$ 与矩阵相乘,带入矩阵快速幂计算一下就行了
求解复杂度 $\mathcal{O(2^3\cdot k\log n)}$

OpenJ_POJ1058 GuidePosts

Vjudge 上的链接
Picks 出的好题
设 $G$ 为题中给出的有向图的邻接矩阵,则答案存在的最终矩阵可以计算为
$$\sum_{i=0}^n{n\choose i} * G^i [k\mid i]$$
然后和上面一样了(实际上上面是别人做了 Picks 题后用矩阵的二项式定理出的
然后就没什么了

LOJ6485 LJJ学二项式定理

题目链接
一开始 sb 了,结果推了好久,后来突然发现前面一个式子推错了,再推一下终于出来了
$$
\begin{eqnarray}
&&\sum_{i=0}^n {n\choose i}\cdot s^i\cdot a_{i \ \ mod \ \ 4} \\
&=& \sum_{k=0}^3 a_k \sum_{i=0}^n {n\choose i}\cdot s^i [i\ \ mod \ \ 4=k] \\
&=& \sum_{k=0}^3 a_k \sum_{i=0}^n {n\choose i}\cdot s^i[4\mid (i-k)] \\
&=& \sum_{k=0}^3 a_k \sum_{i=0}^n {n\choose i}\cdot s^i\big{(}\frac{1}{4}\sum_{j=0}^3\omega_4^{(i-k)j}\big{)}\\
&=& \frac{1}{4}\sum_{k=0}^3 a_k \sum_{j=0}^3 \sum_{i=0}^n {n\choose i} \cdot s^i \omega_4^{(i-k)j} \\
&=& \frac{1}{4}\sum_{k=0}^3 a_k \sum_{j=0}^3 \omega_4^{-jk}\sum_{i=0}^n {n\choose i} \cdot s^i \omega_4^{ij} \\
&=& \frac{1}{4}\sum_{k=0}^3 a_k \sum_{j=0}^3 \omega_4^{-jk} (s^i \cdot \omega_4^{ij}+1)^n
\end{eqnarray}
$$
这时复杂度已经很低了,为 $\mathcal{O(}$$T\log{n}$$\mathcal{)}$ ,可以通过此题

sys_con

OIer,常规 / 竞赛都渣得不行