单位根反演

原理

$$[ d \mid n ] = {1\over d} \sum_{i=0}^{d-1} \omega_d^{in}$$

例题

loj6485 LJJ学二项式定理

首先枚举$i\pmod 4$的余数$t$，然后转化成对于每一个$t$，求

$$\sum_{i=0}^n {n\choose i}s^i [ 4\mid (i-t) ] \\$$

单位根反演：

$$= \sum_{i=0}^n {n\choose i}s^i {1\over 4}\sum_{j=0}^3 \omega_{4}^{j(i-t)} \\ = {1\over 4} \sum_{j=0}^3 \omega_{4}^{-jt} \sum_{i=0}^n {n\choose i}s^i w_4^{ij}$$

最后面的那一坨东西，由二项式定理知$(1+x)^n = \sum_{i=0}^n {n\choose i}x^i$，所以：

$$= {1\over 4} \sum_{j=0}^3 \omega_{4}^{-jt} (s\omega_4^j + 1)^n$$

直接算就可以了。

Code

uoj450【集训队作业2018】复读机

考虑一个复读机复读次数的生成函数：

$$F(x) = \sum_{i=0}^{\infty} {x^i\over i!} [d\mid i]$$

而我们要算的实际上是$n! \cdot F^k(x) [x^n]$。

对$F(x)$进行单位根反演：

$$F(x) = {1\over d}\sum_{i=0}^{\infty} {x^i\over i!} \sum_{j=0}^{d-1} \omega^{ij}\\ = {1\over d}\sum_{j=0}^{d-1} \sum_{i=0}^{\infty} {x^iw^{ij}\over i!}\\ = {1\over d} \sum_{j=0}^{d-1} e^{\omega^j x}$$

$1\over d$是常数，我们先把它忽视掉，最后再在答案里乘上一个$1\over d^k$。

考虑$F^k(x)$的组合意义，相当于对于这$k$个多项式，从每一个里面选一项相乘，所有的方案得到的乘积的和。枚举$e^{\omega^jx}$被选的次数$p_j$，得到

$$F^k (x) = \sum_{p_0+p_1\cdots p_{d-1}=k}k!\prod_{j=0}^{d-1} {1\over p_j!}e^{p_j \omega_jx}\\ = \sum_{p_0+p_1\cdots p_{d-1}=k} e^{(\sum_{j=0}^{d-1}p_jw_j)x} \cdot k!\prod_{j=0}^{d-1} {1\over p_j!}$$

而

$$F^k (x) [ x^n ] = \sum_{p_0+p_1\cdots p_{d-1}=k} {(\sum_{j=0}^{d-1}p_jw_j)^n \over n!} \cdot k!\prod_{j=0}^{d-1} {1\over p_j!}$$

直接计算，复杂度$O(k^d \log n)$。

Code

bzoj3328 PYXFIB

设

$$A = \begin{bmatrix}1 & 0 \\ 1 & 1\end{bmatrix}\\ B = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$$

则我们相当于要求出

$$(\sum_{i=0}^n {n\choose i} A^i [k\mid i] )B$$

对前面的那个括号里面的东西单位根反演，得到

$${1\over k} \sum_{j=0}^{k-1} \sum_{i=0}^n {n\choose i}A^i\omega^{ij} \\ = {1\over k} \sum_{j=0}^{k-1} (\omega^j\cdot A + E)^n$$

其中$E$表示单位矩阵。

直接矩阵快速幂计算，时间复杂度为$O(2^3 \cdot \log n \cdot k)$。

loj3058 「HNOI2019」白兔之舞

设矩阵$A$是满足$A_{i,j} = w(i,j)$的$n\times n$的矩阵。

走$m$步的方案数为${L\choose m}T_{x,y}$，其中$T=A^m$。

则对于每一个$t$，我们需要求出

$$\sum_{m=0}^L {L\choose m}A^m [k\mid (t-m)]$$

单位根反演之后得到

$${1\over k}\sum_{j=0}^{k-1} \omega_k^{-tj}(\omega_k^jA + E)^L$$

对于每一个$j$，分别算出$F_j = (\omega_k^j A+ E)^L$，设$f_j$为$F_j$的$x$行$y$列的元素，则$t$的答案就是

$$Ans_t = {1\over k}\sum_{j=0}^{k-1} f_j \omega_k^{-tj}$$

由于$-tj={t\choose 2}+{j\choose 2}-{t+j\choose 2}$，所以

$$Ans_t = {1\over k}\cdot \omega_k^{t\choose 2} \sum_{j=0}^{k-1} (f_j\cdot \omega_k^{j\choose 2} ) \omega_k^{-{i+j\choose 2}}$$

这是一个卷积的形式，用MTT优化一下就可以了。

总时间复杂度$O(kn^3\log L + k\log k)$。