初中的小朋友正在学习哈希。我也来学一下。
AT_abc250_e [ABC250E] Prefix Equality
这个很简单，去重之后暴力算 hash 最后判断一下就好了。
CF1830C Hyperregular Bracket Strings
感觉比较有趣的题目。
先介绍：长度为 \(2n\) 的序列，构造括号序列的总方案数是 \(C_n = \dfrac{1}{n + 1}\dbinom{2n}{n}\)，也就是卡特兰数。
先考虑要求的所有区间都相离怎么做。设区间长度分别为 \(d_1,d_2,d_3,\cdots,d_n\)，那么因为区间之间互不影响所以答案是 \(\prod_{i = 1} ^n C_{d_i}\)。
那么对于相交的区间 \([l,r]\) 和 \([l',r']\)，不妨设 \(l< l'< r< r'\)，发现这时需要 \([l,l'],[l',r],[r,r']\) 全部合法才行。
互相包含的区间同样如此，也可以拆成三个区间。
我们再参照这样重复的区间组，发现需要把每个区间组的端点全部放进排序，最后相邻两位所组成的区间都要合法。
最后用卡特兰数乘法原理即可。
怎么拆分区间？我们想按照所属区间集合不同的点染成相同颜色，只需要给每个区间附上一个随机权值 \(d\)，之后异或起来区间的所有数就是这一段的颜色。
区间异或可以用差分处理。
CF1418G Three Occurrences
先考虑把 \(x = 3\) 转换一下，变成 $x \leq 3 $ 且 \(3 | x\)。
第一个可以双指针扫过去，第二个桶统计双指针目前扫到的区间中每个位置上出现的数的数量，大小对 \(3\) 取余。
但是发现这样依然比较差强人意，所以对桶哈希，然后开个 map 统计 hash 值。