单位根反演学习笔记

单位根 $\omega_{k}^{1}$ 的含义就是对 $-1$ 开 $k$ 次根号，$\omega_{k}^d$ 就是 $(\omega_{k}^1)^d$。具体的看 $\texttt{FFT}$ 的内容。

对于单位根反演，有一个等式：

$[k\vert d]=\frac 1k\sum_{i=0}^{k-1}\omega_k^{di}$

考虑证明。

• $d\not=0\mod k$

用等比数列求和，可以化为 $\dfrac1k\dfrac{\omega_k^{kd}-1}{\omega_{k}^d-1}$。

由于 $\omega_{k}^k=1$，且 $w_k^d\not=1$，则原式值为 $0$。

• $d=0\mod k$

由于此时和式内每一个数都是 $1$，则原式值为 $1$。

然后可以推到下面这个公式

$\begin{aligned} \text[ a=b\mod n ] &=[a-b=0\mod n]\\ &=[n\vert a-b]\\ &=\frac1n\sum_{d=0}^{n-1}\omega_{n}^{ad}\omega_{n}^{-bd} \end{aligned}$

P5591 小猪佩奇学数学

给定 $n,p,k$，求

$\sum_{i=0}^n\binom ni\times p^i\times\lfloor\frac ik\rfloor \mod 998244353$

其中，$1\le n,p\le 998244353,k\in\{2^w\vert 0\le w\le 20\}$。

推柿子。

$\begin{aligned} \sum_{i=0}^n\binom nip^i\lfloor\frac ik\rfloor &=(\sum_{i=0}^n\binom nip^i\sum_{j=0}^i\frac 1k\sum_{d=0}^{k-1}\omega_k^{dj})-(1+p)^n\\ &=\frac1k\sum_{d=0}^{k-1}\sum_{i=0}^n\binom nip^i\sum_{j=0}^i\omega_{k}^{dj}-(1+p)^n\\ &=\frac1k\sum_{d=0}^{k-1}\sum_{i=0}^n\binom nip^i\frac{\omega_k^{d(i+1)}-1}{\omega_{k}^d-1}-(1+p)^n\\ &=\frac1k\sum_{d=0}^{k-1}\frac{\sum\limits_{i=0}^n\dbinom nip^i(\omega_k^{d(i+1)}-1)}{\omega_{k}^d-1}-(1+p)^n\\ &=\frac1k\sum_{d=0}^{k-1}\frac{\omega_k^d(1+p\omega_k^d)^n-(1+p)^n}{\omega_{k}^d-1}-(1+p)^n \end{aligned}$

根据单位根的定义，$\omega_{k}^1=g^{\frac{mod-1}{k}}$，$g$ 是模数的原根，取 $3$。

还有一个细节，就是你在等比数列求和时，当 $d=0$，则底下的 $\omega_k^d-1=0$，显然是错的，故应该要特判掉 $d=0$ 的情况。

$\begin{aligned} \sum_{i=0}^n\binom nip^i\sum_{j=0}^i\omega_{k}^{dj} &=\sum_{i=0}^n\binom nip^i(i+1)\\ &=\sum_{i=0}^n\binom niip^i+(1+p)^n\\ &=\sum_{i=0}^n\binom {n-1}{i-1}p^{i-1}\times np+(1+p)^n\\ &=np\times(1+p)^{n-1}+(1+p)^n \end{aligned}$

$\color{deeppink}代码$。