多项式应用
习题一
题意
询问有多少序列满足下列条件：
- 序列长度等于 $n$
- 序列由不超过 $m$ 的正整数构成且至少含有一个素数
- 序列所有数之和是 $p$ 的倍数
题解
考虑容斥，于是答案为由不超过 $m$ 的正整数构成的序列数减去不超过 $m$ 的合数构成的序列数。
不超过 $m$ 且模 $p$ 为 $i$ 的正整数个数，而利用线性筛可以计算出不超过 $m$ 且模 $p$ 为 $i$ 的合数个数。
设 $\text{dp}(i,j)$ 表示长度为 $i$ 且和模 $p$ 为 $j$ 的序列数，发现可以利用倍增 $+$ $\text{NTT}$ 转移。时间复杂度 $O(m+p\log n\log p)$。
本题 $p\le 100$ 且模数为合数，所以考虑直接暴力转移，时间复杂度 $O(m+p^2\log n)$。
习题二（字符串匹配）
题意
给定只包含小写字母和通配符的字符串 $A,B$。其中 $A$ 为模板串，$|A|=m,|B|=n$。询问所有匹配位置。
题解
构成字符集到数值的映射
$$ f(x)= \begin{cases} x-a &x= a\sim z\\ 0 &x=* \end{cases} $$
令 $c_i=\sum_{j=0}^{m-1}\left(f(a_j)-f(b_{i-m+1+j})\right)^2f(a_j)f(b_{i-m+1+j})$。
于是 $B$ 中第 $i$ 个字符结尾的长度为 $m$ 的字符串与 $A$ 匹配当且仅当 $c_i=0$。令 $t_i=a_{m-1-i}$，有
$$\sum_{x+y=i}\left(f(t_x)-f(b_y)\right)^2f(t_x)f(b_y)=\sum_{x+y=i}f(t_x)^3f(b_y)+\sum_{x+y=i}f(t_x)f(b_y)^3-2\sum_{x+y=i}f(t_x)^2f(b_y)^2$$
于是直接 $\text{FFT}$ 即可，时间复杂度 $O(n\log n)$。
习题三（差分与前缀和）
题意
给定一个长度为 $n$ 的序列 $a$，求 $a$ 的 $k$ 阶差分或前缀和。
题解
设序列的生成函数为 $F(x)=\sum_{i=0}^{n-1} a_ix^i$，则 $k$ 阶差分等价于
$$ F(x)(1-x)^k=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i{i\choose k}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i\frac {k^{\underline i}}{i!} $$
而 $k$ 阶前缀和等价于
$$ F(x)(1+x+x^2+x^3+\cdots)^k=F(x)(1-x)^{-k}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}(-1)^i\frac {(-k)^{\underline i}}{i!}=\sum_{i=0}^{n-1}a_ix^i\sum_{i=0}^{n-1}\frac {k^{\overline i}}{i!} $$
直接 $O(n)$ 递推出系数然后 $\text{NTT}$ 卷积即可。时间复杂度 $O(n\log n)$。
习题四（矩阵卷积）
题意
考虑快速计算序列 $\{C\}$，其中 $A_i,B_i$ 均为 $w\times w$ 矩阵
$$ C_i=\sum_{j=0}^i A_jB_{i-j}(0\le i\le n) $$
题解
不难发现 $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$，于是 $c_{ij}$ 可以拆分成 $w$ 个卷积。
考虑 $O\left(w^2n\log n\right)$ 预处理出 $\{a_{ij}\}$ 和 $\{b_{ij}\}$ 的 $\text{DFT}$ 结果。然后通过 $c_{ij}=\sum_{k=1}^w a_{ik}b_{kj}$ 可以 $O\left(w^3n\right)$ 计算每个 $\{c_{ij}\}$ 的 $\text{DFT}$ 结果。
最后对每个 $\{c_{ij}\}$ 做 $\text{IDFT}$，总时间复杂度 $O\left(w^2n\log n+w^3n\right)$。
