反演问题

单位根反演

$$ [n|k] = \frac{1}{n}\sum_{i = 0}^{n - 1}\omega_n^{ik} $$ 证明：

若 \([n|k] = 0\)，则 $$ \begin{aligned} \sum_{i = 0}^{n - 1}\omega_n^{ik} =\dfrac{1 - \omega_n^{nk}}{1 - \omega_n^{k}} = 0\newline \end{aligned} $$ 否则有 $$ \omega_n^{ik} = 1 $$ 因此原式为1 。

例题

2021HDU多校第五场B

题意

简化后的题意即对于所有的 \(0 \le i, j < n\) 求 $$ \sum_{p = 0}^{L}\sum_{q = 0}^{L - p}[n|p - i][n|q - j]C_{L}^{p}C_{L - p}^{q}(k - 2)^{L - p - q} $$ \(L \le 10^{18}, n \le 500, k \le 26\)

题解

考虑转化

\[ \begin{aligned} ans_{ij} &=\sum_{p = 0}^{L}\sum_{q = 0}^{L - p}[n|p - i][n|q - j]C_{L}^{p}C_{L - p}^{q}(k - 2)^{L - p - q} \newline &=\sum_{p = 0}^{L}\sum_{q = 0}^{L - p} \frac{1}{n}\sum_{I = 0}^{n - 1}\omega_{n}^{I(p - i)} \frac{1}{n}\sum_{J = 0}^{n - 1}\omega_{n}^{J(q - j)}C_L^p C_{L - p}^q(k - 2)^{(L - p - q)}\newline &=\frac{1}{n^2}\sum_{p = 0}^{L}\sum_{q = 0}^{L - p}\sum_{I = 0}^{n - 1}\sum_{J = 0}^{n - 1}\omega_n^{Ip}\omega_n^{Jq}C_L^pC_{L - p}^q(k - 2)^{L - p - q}\omega_n^{-Ii}\omega_n^{-Jj}\newline &=\frac{1}{n^2}\sum_{I = 0}^{n - 1}\sum_{J = 0}^{n - 1}(\omega_n^{I} + \omega_n^{J} + k - 2)^L\omega_n^{-Ii}\omega_n^{-Jj} \end{aligned} \]

令 \(A_{iI} = \omega_n^{-Ii}, B_{IJ} = \frac{1}{n^2}(\omega_n^{I} + \omega_n^{J} + k - 2)^L, C_{Jj} = \omega_n^{-Jj}\)

可知 \(ans = A\times B \times C\)

注：\(\omega_n^{1} = g^{\frac{P - 1}{n}}\)