7.3 闲话：说循环卷积

· · 个人记录

这篇文章在 7 月 2 日晚上就开始写了，摸了很久到凌晨才写完，所以就变成 7.3 闲话了。写这篇文章主要是因为我最近有做到一些题，同时又有人问到相关内容，（也因为想水文章了）就来闲扯几句。

首先我认为有必要再提一下 DFT 和循环卷积的关系：两个序列分别做长度为 n 的 DFT 后对应项乘起来，IDFT 后得到的就是两个序列做长度为 n 的循环卷积的结果。具体证明可以见这里。

然后就是这样一个性质：

[x^k](f(x) \bmod (x^n-1))=\sum_{d\ge 0}[x^{k+nd}]f(x)

也就是说在模 x^n-1 下做多项式乘法，实际上就是做长度为 n 的循环卷积。这东西有两种证法，一种是直接手动模拟长除法，比较无聊这里就略去了；还有一种是利用这个引理：

那么我们将全部 n 个 n 阶单位根带入 f(x) 计算，根据引理可知这些就是 f(x) \bmod x^n-1 的点值。要变成系数就需要插值，但对于单位根处的点值，插值回去就是做 IDFT。可见这个性质和前一个是本质相同的。

然后我根据最近做到的两道题，再来说一些玩法。

原题链接：QOJ 1254

这题就是说给你个集合 \{0,1,\cdots,T\} 问你有多少个子集的和模 n 为 r，答案模 998244353。这题看起来比较 naive，n 只有 10^4，但是 T 达到了 10^{100000} 量级。（原题中 T 要减一，但我懒就不想在后面写了）

最暴力的 dp 就不说了，设 f(x)=(1+x^0)(1+x^1)\cdots(1+x^{n-1})，g(x)=(1+x^0)(1+x^1)\cdots(1+x^{T \bmod n})，答案就应该是

[x^r] f(x)^{\lfloor T/n \rfloor}g(x) \bmod (x^n-1) 为方便表示，以下设 $t=\lfloor T/n \rfloor$。设 $a_k=[x^k] f(x)^t \bmod (x^n-1)$，根据前面提到的 DFT —— IDFT 法来算循环卷积，就得到 $$a_k=\frac 1n\sum_{j=0}^{n-1}\omega_n^{-kj}\prod_{i=0}^{n-1}(1+\omega_n^{ij})^t$$ 先考虑后面那段乘积，设 $d=\gcd(n,j)$ 就可以写为 $$\left(\prod_{i=0}^{n/d-1}(1+\omega_{n/d}^{ij/d})\right)^{dt}=\left(\prod_{i=0}^{n/d-1}(1+\omega_{n/d}^i)\right)^{dt}$$ 这是因为 $n/d$ 和 $j/d$ 互质，对于 $i\in\{ 0,1,\cdots,n/d-1\}$，$\omega_{n/d}^{ij/d}$ 必然互不相同，也就是说取遍了 $\omega_{n/d}^i$。现在这个形式就比较熟悉了，我们将 $x=-1$ 代入 $$x^n-1=\prod_{i=0}^{n-1}(x-\omega_n^i)$$ 就知道那段连乘应为 $((-1)^n((-1)^{n/d}-1)^d)^t$，现在回到原式 $$a_k=\frac {(-1)^{nt}}{n} \sum_{j=0}^{n-1}\omega_n^{-kj}\left((-1)^{\frac{n}{\gcd(n,j)}}-1\right)^{\gcd(n,j)t}$$ 按照处理这种数论问题的套路，可以尝试枚举 $\gcd(n,j)$： $$a_k=\frac{(-1)^{nt}}{n}\sum_{d|n}((-1)^{n/d}-1)^{dt}\sum_{j=0}^{n-1}\omega_n^{-kj}[\gcd(n,j)=d]$$ 枚举 $j$ 时保证其为 $d$ 的整数倍，即 $$a_k=\frac{(-1)^{nt}}{n}\sum_{d|n}((-1)^{n/d}-1)^{dt}\sum_{j=0}^{n/d-1}\omega_{n/d}^{-kj}[\gcd(n/d,j)=1]$$ 考虑后面这个东西，可以使用 mobius 函数来处理（为了后续方便，这里调换了 $d$ 和 $n/d$）： $$a_k=\frac{(-1)^{nt}}{n}\sum_{d|n}((-1)^d-1)^{nt/d}\sum_{j=0}^{d-1}\omega_d^{-kj}\sum_{p|d,p|j}\mu(p)$$ $$a_k=\frac{(-1)^{nt}}{n}\sum_{d|n}((-1)^d-1)^{nt/d}\sum_{p|d}\mu(p)\sum_{j=0}^{d/p-1}\omega_{d/p}^{-kj}$$ $$a_k=\frac{(-1)^{nt}}{n}\sum_{d|n}((-1)^d-1)^{nt/d}\sum_{p|d}\mu(d/p)p[p|k]$$ 观察前面比较原始的形式，可以发现若 $\gcd(n,k_1)=\gcd(n,k_2)$，则必然有 $a_{k_1}=a_{k_2}$，那么我们只需要对 $n$ 的所有因数求解即可，过程中可以假定 $k|n$。 此时计算 $a$ 的全部项的时间复杂度已经达到了线性，对所有因数直接求出答案的复杂度 $\Theta (d(n)^2 2^{\omega(n)})$ 已经低于 $\Theta (n)$。需要注意的是，这里我们求 $\gcd(n,i)$ 是可以线性筛的 —— 若 $\gcd(a,b)=1$，则 $\gcd(n,ab)=\gcd(n,a)\gcd(n,b)$，证明是显然的。 **** 还有一题是 [SPOJ 26194](https://www.spoj.com/problems/TENALI/)。 这题也是给了你个集合 $\{0,1,\cdots,n-1\}$，问你有多少大小为 $k$ 的子集，元素和是 $n$ 的整数倍，答案模 $10^9+7$。 首先可以直接写出答案的计算式为 $$[y^kx^0]\left(\prod_{i=0}^{n-1}(1+yx^i) \bmod (x^n-1)\right)$$ 这个二元生成函数应该比较容易理解，就不做解释了。那我们还是尝试嗯做 DFT，答案就应该是 $$\frac 1n\sum_{j=0}^{n-1} [y^k] \prod_{i=0}^{n-1}(1+y\omega_n^{ij})$$ 根据上一题的做法，那段乘积也应该是个整系数多项式。没错，它正是 $(1-(-y)^{n/\gcd(n,j)})^{\gcd(n,j)}$。 这个和式中看起来有许多项要算，但实际上非零的只有 $\Theta(k)$ 个。再进一步发现非零项都是等距分布的，设 $d = \gcd(n,k)$ 的话答案就可以写成 $$\frac 1n \sum_{j=0}^{d-1}[y^k](1-(-y)^{d/\gcd(d,j)})^{\gcd(d,j)n/d}$$ 要继续优化，可以考虑枚举 $t=\gcd(d,j)$，答案为 $$\frac 1n\sum_{t|d}[y^k](1-(-y)^{d/t})^{tn/d}\sum_{j=0}^{d-1}[\gcd(d,j)=t]$$ $$=\frac 1n\sum_{t|d}[y^k](1-(-1)^{d/t}y^{d/t})^{tn/d} \varphi(d/t)$$ $$=\frac 1n\sum_{t|d}[y^{kt/d}](1-(-1)^{d/t}y)^{tn/d}\varphi(d/t)$$ $$=\frac 1n\sum_{t|d}\varphi(t)\binom{n/t}{k/t}(-1)^{k/t} (-1)^k$$ 预处理出 $\varphi$ 函数，每组数据时间复杂度大约是 $\mathcal O(\sigma_1(k))$ 的。