水平测试 week 4 简要口胡题解

by Cyanic

---

相信大部分的题目，大家都可以独立或者讨论解决。这里简单写一下 G,H,I,K 的做法。

G

最后只需要输出总和，考虑拆贡献。对于表达式

$$\cdots + abc \times defg \times hijk+ \cdots$$
我们可以拆成若干个形如
$$\cdots + b \cdot 10^2 \times d \cdot 10^4 \times k \cdot 10^0 + \cdots$$
之和。也就是中间有若干个乘法符号隔开，两端取一个加号，中间各取一个带权数位的贡献总和。从每个加号出发，到每个加号，做一个 $O(n^2)$ 的 DP 即可。

H

我们以整行来考虑。随着乘以行的数增大，每个数的位数也会增大（至多 $\log$ 次）。那么总共行的位数总变化次数为 $O(n \cdot \log 10^9)$。进而求出每一行的位数。

对于每个询问先二分出最后再哪一行。接下来我们可以使用主席树或者离线+BIT来维护每一行的各个位数，询问在数据结构上二分即可。

时间复杂度为两个 $\log$，听说有一个 $\log$ 做法，大家可以自行思考 。

I

把它放在 $s-t$ 图图像上，被感染的边界上下都是凸的。先用一个队列搞出上下边界，剩下的直接二分，找到和边界的那一部分先相交。

K

显然是一个二维的多项式乘法。可考虑二维 FFT，有两种实现方法。

可以对行列分别进行 DFT，DFT 对行列实际上是独立的。比如 $f(x,y)$ 可以先看作是关于 $x$ 的多项式，DFT 就将单位根带入求值。接着可以看做是关于 $y$ 的多项式。这样就完成了二维 DFT。实际上 FWT 就是 $n$ 维且每维大小都是 $2$ 的高维 DFT。

也可以将二维转成一维做 DFT，取足够大的 $T> 2M$，令 $g[Tx+y]=f[x][y]$，再做一维 DFT 即可。这种做法不需要对 DFT 进行修改，但是常数也略大。