【习题选讲】zzd《FFT入门》

imily's notebook

2020-07-30

FFT

套路1. 字符串匹配

我们发现匹配的字符对下标之差是定值，翻转其中一个串以后就变成了，匹配的字符对下标之和是定值，这是满足卷积形式的。（好妙啊QAQ，卷积形式真的万能

${[BZOJ4503]}$

不能直接 kmp 啊，通配符的 fail 指针不好定。考虑卷积。

我们希望通过某一位是否为 0 来判断能否在某位匹配上。可以让相同字符差为 0，做一个平方就不会有“正 + 负 = 零”的情况发生。

但通配符怎么搞？它可以与任何字符配啊。我们希望有通配符存在就是 0，那么通配符值 = 0，乘到柿子里去就好了。

$\sum\limits_{i = 1}^n\sum\limits_{j = 1}^ m (S_i - T_j)^2 S_i T_j$

这个东西拆开来，做三次 FFT。

${[CF528D]}$

按照上一题的套路，我们设 $f[i, c]$ 表示 $[A 的位置 i 匹配字符 c]$，$g[i, c]$ 表示 $[B 的位置 i == c]$。相减之后做平方，这个东西展开太困难了，而且要做很多次 FFT，常数爆炸，考虑别的方法。

显然 $f[i, c]$ 和 $g[i, c]$ 只是 0/1，若 $A[i]$ 能匹配上 $B[j]$，那么存在一个 $c$，$f[i, c] \times g[j, c] = 1$。

发现字符集很小，我们分别对每种字符做一次卷积，若位置 i 的四种值之和 == $|B|$ 则位置 $i - |B| + 1$ 可以匹配。复杂度$O(4nlogn)$.

套路2. 卷积形式变形

常用技巧是翻转和更换求和指标。

${[ZJOI2014]-力}$

自己还推了一部分，hh

设 $F(i) = \frac{1}{i^2}$，$G(i) = q_i$，一些不合法的下标，值为 0.

$E(i) = (\sum\limits_{j = 0}^iF(j) \times G(i - j)) - (\sum\limits_{j = i}^m F(j - i) \times G(j))$

第一个括号里是裸的卷积形式，第二个括号要再做一做。

更换求和指标：

$\sum\limits_{j = 0}^{m - i} F(j) \times G(j + i)$

翻转：（其中 $G^r(i)$ 表示 $G(m - i)$）

$\sum\limits_{j = 0}^{m - i} F(j) \times G^r(m - i - j)$

套路3. 背包问题相关

${[CF286E]-Ladies’ Shop}$

比较自然的想法，f[a[i]] = 1，f[0] = 1，f 与自己做卷积，做最多 m 次就得到了所有能表示的数。但这样是 O(m log^2 m)的。

但其实并不用做 m 次。实际上一次卷积就能得出答案。

一次卷积后，那些 f[i] > 2 的 i 就是可以省略的。为什么？初始一次，f[i] 与 f[0] 相乘一次，还有其他能组成 i 的数字的贡献… 反过来说，f[i] = 2 的 i 就是必选的。

套路4. 分治FFT

（好难啊 QAQ 我没有脑子）

${[Lydsy1704月赛]-二元运算}$

先不考虑括号里的限制。加法可以直接算，减法要变一下：

$ans_k = \sum\limits_{i = k}^n a_i \times b_{i - k}$ $ans_k = \sum\limits_{i = 0}^{n - k} a_{i + k} \times b_i$

翻转，再将 ans 下标加 n，凑一个卷积形式：

$ans_{n + k} = \sum\limits_{i = 0}^{n - k}a_{i + k} \times b_{n - i}^r$

考虑括号里的限制，容易发现在值域上，左区间对右区间一定有贡献，于是想到分治值域。具体来说，对于每个数值区间 [l, r]：

$x = y$: 贡献给 $0$
$x < y$: $a[l, mid]$ 卷 $b[mid + 1, r]$
$x > y$: $a[mid + 1, r]$ 卷 $b[l, mid]$

（我今天才知道在递归过程中计算一个子问题对另一个子问题的贡献的分治就叫 CDQ 分治？？？）

${[CF553E]-Kyoya and Train}$

乍一看更像是 dp 题，于是考虑 dp：$f[i, j]$ 表示到 $i$ 位置耗时 $j$ 的最小期望代价，$f[x, t] = min\{c(x, y) + f[y, t + k] \times P_{e, k}\}$，其中 P 表示经过 e 边耗时 k 的概率。

注意到后面那坨东西可以翻转变成卷积形式，然后这玩意就是分治 FFT 啦，分治时间，对于 $[l, r]$ 先做 $[mid, r]$ 再做 $[l, mid)$。复杂度 $O(mTlog^2T)$.

杂题

${[BZOJ3160]-万径人踪灭}$

我们先忽略条件 2，最后减去条件 2 的就好了（用 manacher 算）

按照朴素的解法，展开做多次 FFT 也是可以的，然而还有更简便的方法。考虑只有 a 和 b，分开来做再同一位置的相乘，正确性显然。

${[Cerc2015]-Frightful Formula}$

首先假装已经知道这是 FFT 题！然后快乐推柿子。显然答案只分为 $(i, 1)/(1, i)$ 初始值的贡献和 $(i, j)$ 额外加上的 $c$ 的贡献。

$(i, 1)/(1, i)$:

$\sum\limits_{i = 1}^n C(n - i + n - 1, n - i)\times a^{n - i} b^{n - 1}$

$(i, j)$:

$\sum\limits_{i = 2}^n \sum\limits_{j = 2}^n C(n - i + n - j, n - i) \times a^{n - i} b^{n - j} c$

设 $A_i = \frac{a^{n - i}}{(n - i)!}$, $B_i = \frac{b^{n - i}}{(n - i)!}$:

$c\sum\limits_{i = 2}^n \sum\limits_{j = 2}^n (2n - i - j)! \times A_iB_j$

枚举 i + j:

$c\sum\limits_{i = 4}^{2n} (2n - i)! \sum\limits_{j = 2}^{i - 2} A_jB_{i - j}$

这就是卷积形式了。

${[Hnoi2017]-礼物}$

我们设得到序列为 a 和 b，设给 a 每一位加 c

$ans = \sum (a_i + c - b_i)^2$ $ans = \sum a_i^2 + \sum b_i^2 + n \times c^2 + 2c \times (\sum a_i - \sum b_i) - 2 \sum a_ib_i$

和 c 有关的项可以枚举或用二次函数求极值，最后一项用卷积求，考虑怎么搞，显然将 a 翻转后复制一份就好啦。

${[CF958F3]-Lightsabers(hard)}$

把每种颜色能选的 01 生成函数乘起来，朴素做法会 TLE，考虑启发式合并，堆 + vector 维护。$O(nlog^2n)$

（分治也能做！

${[CF623E]-Transforming Sequence}$

显然 $n > k$ 的时候无解。

容易发现跟数值具体大小没有关系，关键是每次都有新的二进制位被填上。

小数据的话可以 dp，$f[i, j]$ 表示前 $i$ 个数有 $j$ 个二进制位为 $1$，转移 $f[i, j] = \sum\limits_{k = 0}^{j - 1} f[i - 1, k] \times 2^k \times C(j, k)$，其中 $2^k$ 表示原来已有的可放可不放。

考虑优化：

$\frac{f[i, j]}{j!} = \sum\limits_k \frac{f[i - 1, k] \times 2^k}{k!} \times \frac{1}{(j - k)!}$

这样是 $O(n^2 log n)$ 的，然后我就想不出了。。但还能优化！！考虑到这样一次一次转移太慢了，我们加大转移的步长，倍增，合并每段的 dp 值，相当于 dp[n & (2 ^ 0)] 卷 dp[n & (2 ^ 1)] … 卷dp[n & (2 ^ 最高位)]，这样就能在 $O(k log^2 k)$ 的时间复杂度内求出了。