$$c_k=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}[i+j\bmod p=k]a_ib_j$$

对序列 $A,B$ 做长度为 $n$ 的 $\text{FFT}$ 等价于求序列 $A,B$ 的循环卷积。

考虑单位根反演证明

$$ \begin{equation}\begin{split} c_k&=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}[i+j\bmod p=k]a_ib_j\\ &=\frac 1n\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\sum_{d=0}^{n-1}w_n^{d(i+j-k)}a_ib_j\\ &=\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}w_n^{di}a_iw_n^{dj}b_j\\ &=\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}\left(\sum_{i=0}^{n-1}a_iw_n^{di}\right)\left(\sum_{j=0}^{n-1}b_jw_n^{dj}\right) \end{split}\end{equation} $$ 不难发现 $\left(\sum_{i=0}^{n-1}a_iw_n^{di}\right)\left(\sum_{j=0}^{n-1}b_jw_n^{dj}\right)$ 即为原来的 $\text{DFT}$ 过程，$\frac 1n\sum_{d=0}^{n-1}w_n^{-dk}$ 即为原来的 $\text{IDFT}$，证毕。

事实上普通的卷积计算相当于长度为 $2^n$ 的循环卷积计算，只是循环卷积长度大于 $C$ 序列的长度，所以循环卷积结果即为普通卷积结果。

考虑 $\text{DFT}$ 过程，有

$$ \begin{equation}\begin{split} y_k&=\sum_{i=0}^{n-1}a_iw_n^{ki}\\ &=\sum_{i=0}^{n-1}a_iw_n^{{k+i\choose 2}-{k\choose 2}-{i\choose 2}}\\ &=w_n^{-{k\choose 2}}\sum_{i=0}^{n-1}\left(a_iw_n^{-{i\choose 2}}\right)w_n^{{k+i\choose 2}} \end{split}\end{equation} $$

其中 ${n\choose 2}$ 表示组合数。易知上式可以通过普通卷积求解，$\text{IDFT}$ 过程类似。

值得一提的是，循环卷积的求逆、快速幂等操作直接对 $\text{DFT}$ 的点值进行相应运算即可。

洛谷p5293

给定一个二维 $[L+1]\times n$ 的空间，其中 $(u_1,v_1)\to (u_2,v_2)$ 有 $w_{v_1,v_2}$ 条重边。

假设起点为 $(0,x)$，终点为 $(\ast,y)$($\ast$ 为任意值)，路径长度 $m$ 定义为路径的边数。

对每个 $0\le t\lt k$，求满足所有 $m\equiv t\pmod k$ 且横坐标单增的路径数模 $p$ 意义下的值。

数据保证 $p$ 为素数，$k\pmid p$