标签：le frac sum 单位根 反演 binom omega 小记

反演公式

\[[n | v] = \frac{1}{n}\sum_{0 \le j < n}(\omega_n^v)^j \]

证明很简单，等比数列求和即可。

应用

牛客Wannafly挑战赛11E 白兔的***难

题意：

给定 \(k \le 2^20, n \le 10^{16}, p = 998244353\)，求 \(t \in [0, k)\)，\(a_t =\sum_{k | i,0 \le i + t \le n} \binom{n}{i + t}\)。

思路：

直接单位根反演：

\[\begin{aligned} \sum_{k | i,0 \le i + t \le n} \binom{n}{i + t} &= \sum_{0 \le i\le n} \binom{n}{i}[k | i - t]\\ &= \sum_{0 \le i\le n} \binom{n}{i}\frac{1}{k}\sum_{j = 0}^{k-1}(\omega_{k}^{i -t})^j\\ &= \frac{1}{k}\sum_{j = 0}^{k-1}\omega_{k}^{-tj}\sum_{0 \le i\le n} \binom{n}{i}\omega_{k}^{ij}\\ &= \frac{1}{k}\sum_{j = 0}^{k-1}\omega_{k}^{-tj}(1 + \omega_k^j)^n\\ \end{aligned} \]

不妨令 \(y_j = (1 + \omega_k^j)^n\)，则上式就是一个 IDFT 形式的东西，利用 NTT 解决即可。

P5293 [HNOI2019] 白兔之舞

设 \(W\) 是 \(n \times n\) 的邻接矩阵，则我们有走 \(m\) 步的方法数等于：

\[\binom{L}{m}W^m \]

所以我们要求的就是对于所有 \(t\)：

\[\sum_{m=0}^L\binom{L}{m}W^m[k | m - t] \]

单位根反演可以化为：

\[\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{-tj}(1 + \omega_k^jW)^m \]

不妨设 \(A_j = (I + \omega_{k}^jW)^L\)，\(a_j\) 为 \(W\) 中编号第 \(j\) 个的系数，则我们要求的就是 \(IDFT(a)\)。使用 MTT 即可解决。

【牛客Wannafly挑战赛23 F】计数

直接大力推式子：

\[\begin{aligned} ANS &= \sum_{T}[k | \sum_{e \in T}val_e]\\ &= \frac{1}{k}\sum_{T}\sum_{j=0}^{k-1}(\omega_{k}^{\sum_{e \in T}val_e})^j\\ &= \frac{1}{k}\sum_{j=0}^{k-1}\sum_{T}\prod_{e \in T}(\omega_k^{j})^{val_e} \end{aligned} \]

转化成标准的矩阵树定理形式求解，时间复杂度 \(O(kn^3)\)。

标签：le,frac,sum,单位根,反演,binom,omega,小记
From： https://www.cnblogs.com/rlc202204/p/18161998