# 2022-2-15 Test

link

sol

# A

如果你注意到题面中写明的 $|s|\le 20$ 你会得到直接爆 trie 的 $20\sum|t|$ 做法，然后你以为你通过了此题

如果你注意到数据中写明的 $\sum|s|\le 1e5$ 你会得到一个二进制分组 + ACAM/SAM 的做法 ，然后你真的通过了此题

具体的，你维护 $\mathrm log$ 个 ACAM ，假如此时是第 $k$ 个修改后，你就把 $k$ 二进制分组后每 $2^x$ 个串插一个 ACAM 就好

由于 fail 树的奇异性质，你匹配一个模式串时，在 trie 上匹配到的 $u$ 点的 fail 子树和就是它的子串权值和

合并直接重构

# B

设 $G(m)$ 表示行两两不同，至多有 $m$ 个列等价类的方案数，显然有个简洁的表达 $G(m)=(c^m)^{\underline n}$ 。

设 $F(m)$ 表示恰好有 $m$ 个列等价类的方案数

$$F(m)=\sum_{i=0}^m \begin{Bmatrix}m\\i\end{Bmatrix} G(i) \to\\ G(m)=\sum_{i=0}^m (-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix}F(i)$$

# C

每个数字 $\le 500$ ，所以大于 $\sqrt{500}$ 只有一个，而小于 $\sqrt{500}$ 只有 $8$ 个，于是使用 $dfs$ 算出前八个质数在答案中的分布，然后贪心即可。