AtCoder Beginner Contest 367 题解(E~G)

E

转换关系看作有向边，\(n\) 点 \(n\) 边构成基环树森林，基环树森林k后继唯一，记 f[i][j] 为点 \(i\) 的 \(2^j\) 级祖先，随便倍增。

F

一眼哈希，不知道有没有不哈希的做法。

在这里我们不关心元素的顺序，只关心元素是否出现以及出现几次，考虑一个 \(n\) 位 \(n+1\) 进制数，\(a_i\) 出现一次就在 \(a_i\) 位上 \(+1\)，最多加 \(n\) 次不会出现进位，最终得到的数就反映了元素的出现次数，并且是唯一的。在此基础上就和字符串哈希类似了，选两个素数 \(\ge n+1\) 当基数做双哈希就行了。

收集了一些 HL 群里的做法：

1.对原序列随机赋权，hash值是区间权值和(sum hash)或区间权值异或和(xor hash)，还有人找到了原题(超级加强版)。