卷积
概念
令 $A,B,C$ 分别为三个多项式
形如 $c[k]=\sum_{i\oplus j=k}a[i]b[j]$ 的式子称为卷积，其中 $\oplus$ 为某种运算
注意到多项式的乘法就是加法卷积
化成卷积形式的小技巧
减法卷积，下面默认 $A,B,C$ 的长度都是 $n$
$C_k=\sum_{i=k}^nA_{i-k}B_i=\sum_{i=0}^{n-k}A_{n-k-i}B’_{i}$，其中 $B’_k=B_{n-k}$
证明：
FFT
简介
$FFT$ 最早用于解决多项式乘法，也就是加法卷积
可以将 $O(n^2)$ 的多项式乘法加速到 $O(n\log n)$
与多项式有关的几个概念和约定
多项式的系数表示法：$A(x)=\sum_{i=0}^{n-1}a_ix^i$，次数为 $n$
多项式的点值表示法：$(x_1,y_1),(x_2,y_2),\cdots ,(x_n, y_n)$，一个 $n$ 次多项式可以被 $n$ 个点所唯一确定
单位根
在复平面中，$x$ 表示实数，$y$ 表示虚数，从原点 $(0,0)$ 到 $(a,b)$ 的向量表示复数 $a+bi$
模长：复数 $a+bi$ 的模长为 $\sqrt {a^2+b^2}$，同时这也是其向量的长度
幅角：假设以逆时针为正方向，从 $x$ 轴正半轴到已知向量的转角的有向角叫做幅角
在代数中 $z^n=1$，则称 $z$ 为 $n$ 次单位根，我们将其扩展到复数域，用 $\omega_{n}$ 表示 $n$ 次单位根
至于 $\omega_n$ 的值，我们考虑用欧拉公式计算
然后我们能够发现关于单位根的三个显然的性质
- $w_{dn}^{dk}=w_n^k$
- $w_n^{k+\frac{n}{2}}=-w_n^k$，此处 $2|n$
- $\sum_{k=0}^{n-1}w_n^{k}=[n=1]$
FFT的原理
能够发现用过系数表示的两个 $n$ 次多项式相乘的是时间复杂度为 $O(n^2)$
而用点值表示的两个 $n$ 次多项式相乘的是时间复杂度为 $O(n\log n)$
那么我们考虑是否存在低于 $O(n^2)$ 的算法可以将一个多项式在系数表达和点值表达之间转换呢？
我们考虑将 $n$ 次单位根作为点值表达，然后考虑化简
不妨假设 $n$ 为 $2$ 的幂，其中 $k$ 是表示我们要计算将 $\omega_{n}^k$ 带入的值，不妨令 $k<\frac{n}{2}$
能否发现我们将 $n$ 的规模缩小了一半，且形式完全一样，所以我们可以递归计算，时间复杂度 $O(n\log n)$
现在还剩一个问题，我们还需要将点值表达转换为系数表达
考虑这样一个矩阵
我们现在知道 $y_0$ 到 $y_{n-1}$
那么我们只需要乘前面那个矩阵的逆矩阵就能得到 $a_0$ 到 $a_{n-1}$ 了
首先前面那个矩阵的第 $i$ 行第 $j$ 列的元素是 $w_n^{ij}$，假定从 $0$ 到 $n-1$ 编号
通过一些不为人知的方法 我们得到逆矩阵是 $\frac{w_n^{-ij}}{n}$
我们来验证一下，$a_{i,i}=\sum_{k=0}^{n-1}w_{n}^{ik}\frac{w_n^{-ik}}{n}=1$
$a_{i,j}=\sum_{k=0}^{n-1}w_n^{ik}\frac{w_n^{-jk}}{n}=\frac{1}{n}w_n^{i-j}\sum_{k=0}^{n-1}w_n^{k}$
我们知道 $\sum_{k=0}^{n-1}w_n^k=[n=1]$ 那么 $a_{i,j}=0$
所以现在我们的系数变成 $w_n^{-k}$ 了，再做一次 FFT 就好了
FFT的实现
递归
1 | void FFT(int n, Complex *a, int type) { |
注意到递归版本的常数太大，我们考虑使用非递归的版本
大概就是直接将所有系数换到递归底层的位置，然后合并即可
1 | struct Complex { |
精度比较好的写法，开long double可以跑1e15
1 | typedef std::vector<int> Poly; |
NTT
$FFT$ 使用的是复数，不仅运算慢，而且还有可能产生精度损失
所以我们考虑取模意义下的一种新的单位根
经过前人的努力，我们得知这种数是原根
实际上 $w_n^k=g^{\frac{p-1}{n}}$，这也就表示了 $p$ 必须能被 $2$ 大次幂的整除
常用的模数是 $998244353=119*2^{23}+1$ 原根是 $3$
还有 $1004535809$ 原根是 $3$
1 |
|
比较快的 $NTT$
1 | typedef std::vector<int> Poly; |
不知道为什么有奇怪错误的 $NTT$
1 | typedef std::vector<int> Poly; |
不知道为什么偶尔会出错的 $NTT$
1 | typedef std::vector<int> Poly; |
三模NTT
注意精度在 $10^{26}$ 左右， 正常多项式乘法的极值是 $10^{23}$ 足以通过
1 | int p; |
MTT
四次 $FFT$，$1e9$ 内模数均可
1 |
|
模x^2乘法NTT
单位元 $(0,1)$，$(x,y)$ 逆元 $(-\frac{x}{y^2},\frac{1}{y})$
1 | struct Int { |
集合运算卷积
FWT
大概就是求这个东西 $C_k=\sum_{i\oplus j=k}A_iB_j$，其中 $\oplus$ 表示某中位运算
$FMT$ 一般用于解决 $or$ 和 $and$ 的情况
首先我们考虑 $or$ 的情况，类似 $FFT$ 的做法，我们考虑构造出一种类似点值表达式的东西
在 $or$ 中我们使用的是这个东西，$A’_i=\sum_{j|i=i}A_j$，这样我们就可以直接将 $A’$ 和 $B’$ 直接对应位相乘，然后再变换回去
实际上这个变换就是求一个高维前缀和，但是我们也可以参照 $FFT$ 的写法来实现，本质上是一样的
$and$ 的做法同理
$FWT$ 用来解决 $xor$ 的问题，大概用不到过程吧，这里就不写了
1 | typedef std::vector<int> Poly; |
子集卷积
大概就是求 $C_{k}=\sum_{\\i ~or~j=k\wedge i ~and ~ j=0}A_iB_j$
我们考虑一般的或卷积，注意到第二个限制相当于 $|i|+|j|=|i~or~j|$，所以我们再开一维记录大小即可
时间复杂度 $O(n\log^2 n)$
1 | typedef std::vector<int> Poly; |
分治FFT以及分治FWT
分治 $FFT$，我们给定 $f_0$，以及 $f_k=\sum_{i=0}^{k-1}f_ig_{k-i}$，求 $f$
1 | void solve(Poly &A, const Poly &B, int l, int r) { // 区间左闭右开 |
分治 $FWT$，我们给定 $f_0$，以及 $f_k=\sum_{i=0}^{k-1}f_ig_{k\oplus i}$，其中 $\oplus$ 表示某一种位运算
1 | void solve(int l, int r) { // 区间是左闭右开的形式，另外这个算的是先计算右半部分的 |
例题
简要题意：对于 $S$ 的每个长度为 $|T|$ 的子串求是否和 $T$ 完美匹配，$S$ 和 $T$ 均含有通配符，$|S|\le 3\times 10^5$
简要题解：构造函数 $(S_i-T_i)^2\times S_i \times T_i$
利用这个函数直接将 $S$ 和翻转后的 $T$ 卷起来
简要题意：对于 $S$ 的每个长度为 $|T|$ 的子串中，有多少子串满足与 $T$ 串 $k,k\in [0,m]$ 匹配，$k$ 匹配定义为有至多 $k$ 个位置不同
简要题解：构造函数 $(S_i-T_i)^2\times S_i \times T_i$
对于 $T$ 的每一种字符单独求失配个数
简要题意：现在有 $n$ 个人，第 $i$ 个人手里有一个数字 $i$，现在开始传数字，第 $i$ 个人会将他手里的数字传给 $p_i$，$p_i$ 是一个排列，同时现在有 $m$ 次询问，每次询问给出一个整数 $x$，求传了 $x$ 轮后，每个人的编号乘上他手里的数字的和
$n\le 2\times 10^5,m\le 10^5,x\le 10^9$
简要题解：注意到传球形成了若干个简单环，我们对每个简单环单独计算贡献
我们设当前环的大小为 $n$，第 $i$ 个人的编号为 $a_i$，如果传了 $k$ 轮，那么总贡献是类似于 $\sum a_i\times a_{i+k}$ 的东西，稍作考虑后可以发现这是一个类似减法卷积的东西，将长度扩大到 $2n$，然后再稍作处理直接做减法卷积即可，注意到总贡献刚好是 $1e15$ 级别的，所以我们是可以用 $FFT$ 的
然后考虑处理询问，注意到大小不同的环的个数只有 $O(\sqrt n)$，所以每次询问暴力所有环的大小即可
时间复杂度 $O(n\log n+q\sqrt n)$
简要题意：给定两个长度均为 $n$ 的序列 $a_i,b_i$，定义一个数对 $(a_i,b_j)$ 的价值为 $a_i\times b_j$，现在每个 $a_i$ 和 $b_i$ 都只能使用一次，求对于 $k\in[1,n]$，选出 $k$ 个数对的最大价值和以及最小价值和
$n\le 10^5,-10^4\le a_i,b_i\le 10^4$
我们只需要考虑最大价值和，求最小价值和只需要将其中一个序列全部取反用同样的方法做即可
我们首先考虑如果没有负数，那么最大价值和一定是将 $a$ 和 $b$ 排序后对应位置匹配，如果有负数的话，能够发现，我们一定先凑价值为正的数对，即正正匹配，负负匹配，注意到这里的匹配也是按照绝对值的大小对应位置匹配
我们现在考虑剩下的那一段，可以发现，一定是一个序列全负，一个序列全正，我们按照绝对值递增来排序，可以发现我们如果我们需要在这里选 $k$ 对，那么匹配一定是 $\sum_{i=0}^ka_ib_{k-i}$，很显然这是一个卷积的形式，观察一下权值范围为 $10^{13}$，可以直接使用 $FFT$，时间复杂度 $O(n\log n)$
2021-2022 ACM-ICPC Latin American Regional Programming Contest B Because, Art!
简要题意：数轴上有 $n + 1$ 个点，分别为 $[0,n]$，你现在在 $0$，从 $i$ 走到 $i+1$ 需要花费 $c_i$ 的时间，有 $p_i$ 的成功概率，$(1-p_i)\frac{w_j}{\sum_{k=1}^iw_k}$ 的概率走到 $i-j(1\le j\le i)$，求走到 $n$ 的期望时间
$n\le 10^5$
简要题解：令 $f_i$ 为从 $i$ 走到 $n$ 的概率，容易得到转移为 $f_i=c_i+p_if_{i+1}+\frac{1-p_i}{\sum_{j=1}^iw_j}\sum_{j=0}^{i-1}f_jw_{i-j}$
注意到后面的 $sum$ 很像是一个分治 $NTT$ 的形式，但是注意到我们的转移成环，但是对于这个形式，我们可以简单移项解决，我们可以得到 $f_{i+1}=\frac{1}{p_i}(f_i-c_i-\frac{1-p_i}{\sum_{j=1}^iw_j}\sum_{j=0}^{i-1}f_jw_{i-j})$，同时我们已知 $f_n=0$，要求 $f_0$，那么我们可以设 $f_i=a_if_0+b_i$，注意到 $a_i$ 和 $b_i$ 之间没有联系，可以直接拆成两个式子，这两个式子都是分治 $NTT$ 的形式，直接做即可，时间复杂度 $O(n\log^2n)$
简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $\sum_{i=1}^n\sum_{j=i+1}(a_i\times a_j\bmod P)$，注意只对乘积取模，$P=200003$
$n\le 2\times 10^5$
简要题解：我们注意到如果不是只对成绩取模，那么显然可以直接 $FFT$，那么现在这种情况我们只能通过枚举值为 $x$ 和值为 $y$ 的乘积取模在乘上方案来计算答案
注意到 $P$ 是素数存在原根，那么我们转为枚举 $g^x$ 和 $g^y$，我们知道 $g^x\times g^y=g^{x+y}$ 这个东西符合卷积的形式，使用 $FFT$ 即可，时间复杂度 $O(n\log n)$