我感觉这东西还蛮有意思的。
基础结论
我们首先给出一个结论：\(\sum\limits_{i=0}^{n-1}\omega_n^{ij}=n[n|j]\)，其中 \(\omega_n\) 表示 \(n\) 次单位根，具体的，它等于 \(e^{\frac{2i\pi}{n}}\)。
下面给出证明：
记 \(f(x)=\sum\limits_{i=0}^{n-1}x^i\)，上式就等价于 \(f(\omega_n^j)=[n|j]\)。
- 当 \(\omega_n^i=1\)，即 \(n|j\) 时，原式 \(=\sum\limits_{i=0}^{n-1}1=n\)。
- 当 \(\omega_n^i\ne 1\)，即 \(n\nmid j\) 时，\(f(x)=\dfrac{x^n-1}{x-1}\)，有因为 \((\omega_n^i)^n=1\)，所以原式 \(=0\)。
这个式子的一般情况只能处理 \(j\bmod n=0\) 的情况，考虑拓展成 \(j\bmod n=a\) 的情况。
\(n[j\bmod n=a]=n[(j-a)\bmod n=0]=\sum\limits_{i=0}^{n-1}\omega_n^{i(j-a)}=\sum\limits_{i=0}^{n-1}\omega_n^{ij}\omega_n^{-ia}\)。
这样我们就可以得到拓展，记多项式 \(F(x)=\sum\limits_{i=0}^ma_ix^i\)。
则 \(\sum\limits_{i=0}^ma_i[i\bmod n=k]=\dfrac{1}{n}\sum\limits_{i=0}^ma_i\sum\limits_{j=0}^{n-1}\omega_n^{ij}\omega_n^{-jk}=\dfrac{1}{n}\sum\limits_{j=0}^{n-1}\omega_n^{-jk}\sum\limits_{i=0}^ma_i\omega_n^{ij}=\dfrac{1}{n}\sum\limits_{j=0}^{n-1}\omega_n^{-jk}F(\omega_n^j)\)。
这样，我们就得到了快速求出 \(F(x)\) 所有满足 \(i\bmod n=k\) 的 \(a_i\) 的系数和。
CTT 2019 D2T1 循环序列
可以将题意转化为 \(ans=\sum\limits_{i=0}\binom{k}{ni+x}\bmod p\)，保证 \(n|p-1\)。
不难得到：\(ans=[t^x]\left[(1+t)^k\bmod t^n\right]\)。记 \(f(t)=(1+t)^k\)，所以最终答案为 \(\sum\limits_{i=0}^{n-1}\omega_n^{-ix}f(\omega_n^i)\)。
复杂度为 \(O(n\log n)\)。
快速求值
有的时候暴力数其实并不够，有时候我们需要更快速的求值方式。
IDFT
学过 FFT 和 NTT 的式子，可以发现 IDFT 有着和单位根一致的结构，其实 IDFT 就是使用单位根反演来证明正确性的。
\(f_i=\sum\limits_{j=0}^{n-1}\mathcal{F}_j\omega^{-ij}\)，所以我们可以使用 IDFT 的过程来做到 \(O(n\log n)\) 求解，复杂度 \(O(n\log n)\)，但仅限于 \(n=2^w\) 的情况。
而对于 \(n\neq 2^w\) 的情况，我们就需要考虑其他的求解方式了。
Chirp Z-Transform
我们记 \(F(x)=\sum\limits_{i=0}^{n-1}\mathcal{F}_ix^i\)，则我们最终要求的就是 \(F(x)\) 的 \(n\) 个点值：\(F(\omega_n^i),i=0,1\dots n-1\)。
而这个过程，就是 Chirp Z-Transform 所求解的形式。
针对单位根繁衍的情况，我们可以可以得到：
\(f_i=\sum\limits_{j=0}^{n-1}\mathcal{F}_j\omega^{-ij}=f_i=\sum\limits_{j=0}^{n-1}\mathcal{F}_j\omega^{\binom{i}{2}+\binom{j}{2}-\binom{i+j}{2}}\)。
所以 \(f_i=\omega_n^{\binom{i}{2}}\sum\limits_{j=0}^{n-1}\mathcal{F}_j\omega_n^{\binom{j}{2}}\times \omega_n^{-\binom{i+j}{2}}\)，这个是差卷积的形式，直接卷积即可，复杂度 \(O(n\log n)\)。
例题
Luogu P5591 小猪佩奇学数学
给定 \(n,p,k\)，求 \(\sum\limits_{i=0}^n\dbinom{n}{i}p^i\left\lfloor\dfrac{i}{k}\right\rfloor\bmod 998244353\)，保证 \(\exists w\in \mathbb{N}\cap[0,20],k=2^w\)。
先推式子：
先考虑前者，我们知道 \((1+x)^n=\sum\limits_{i=0}^n\binom{n}{i}x^i\)，而 \([(1+x)^n]'=\sum\limits_{i=0}^n\binom{n}{i}(x^i)'\)，即 \(n(1+x)^{n-1}=\sum\limits_{i=0}^n\binom{n}{i}ix^{i-1}\)。
所以 \(\sum\limits_{i=0}^n\dbinom{n}{i}p^ii=np(1+p)^{n-1}\)。
再考虑后者，很明显是单位根反演的形式，记 \(f(x)=(1+px)^n\)，则可知 \(\sum\limits_{i=0}^n\dbinom{n}{i}p^i[i\mod k=j]=\dfrac{1}{k}\sum\limits_{i=0}^{k-1}f(\omega_k^i)\)，由于 \(k=2^w\)，可以直接使用 IDFT 的过程。
复杂度 \(O(k(\log k+\log n))\)。
[HNOI2019] 白兔之舞
首先考虑使用占位符 \(x\) 表示长度，记 \(F_{i,j}(x)\) 表示走到 \((i,j)\) 的方案数的生成函数，\(S_{i,j}(x)\) 表示对于 \(F_{i,j}(x)\) \(i\) 维的前缀和。
记 \(S_{L,y}(x)=\sum\limits_{i=1}^La_ix^i\)，则我们最终需要的就是 \(\sum\limits_{i=1}^La_i[i\mod k=j],j=0,1\dots k-1\)。
也就是要求解 \(\sum\limits_{i=0}^{k-1}S_{L,y}(\omega_k^i)\omega_k^{-ij},j=0,1\dots k-1\)。
首先考虑如何求出 \(S_{L,y}(\omega_k^i),i=0,1\dots k-1\)。
我们知道 \(F_{i,j}(x)=\sum\limits_{k=1}^nv_{k,j}xS_{i-1,k}(x)\)，\(S_{i,j}=S_{i-1,j}+F_{i,j}=S_{i-1,j}+\sum\limits_{k=1}^nv_{k,j}xS_{i-1,k}(x)\)。
初始状态为 \(S_{0,i}(x)=[i=x]\)。
由此，\(S_{i,j}=S_{i-1,j}+F_{i,j}=S_{i-1,j}+\sum\limits_{k=1}^nv_{k,j}xS_{i-1,k}(x)\)，是可以使用矩阵快速幂的。
然后使用 Chirp Z-Transform 求解后半部分即可，由于是给定模数，所以要使用 MTT。
通过代码。