# 2022-2-15 Test

link

sol

# A

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

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

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

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

合并直接重构

# B

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

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

F(m)=i=0m{mi}G(i)G(m)=i=0m(1)mi[mi]F(i)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

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

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝