观察
我们称 \(x\) 在一段序列中的“位置集合”为 \(x\) 出现的下标的集合。注意到，两段序列能够匹配，当且仅当两段序列的 \(1 \sim m\) 中的数的位置集合构成的多重集相等。快速比较集合，考虑哈希。
哈希
先实现一个从整数到整数的哈希 \(f(x)\)。使用这个哈希的目的是为了提高随机性，防止被卡。
再考虑两个哈希（都使用自然溢出）：
-
\(H(S)\)：把位置集合映射为一个整数。其中位置集合指的是数字 \(x\) 在集合序列 \(A\) 或 \(B\) 中出现的的下标的集合。
用 sum hash 实现： \(H(S)= \sum_{x \in S} f(x)\)。sum hash 的一个好处是，每次加入或删除位置集合中的一个元素，时间复杂度是 \(O(1)\)。这里直接对 \(x\) 求和（应该）也是可行的，但对 \(f(x)\) 求和能够提高随机性。
-
\(G(T)\)：把整数的多重集 \(T\) 映射为一个整数。（这里的多重集指的就是位置集合的哈希值构成的集合。）
仍然使用 sum hash：\(G(T) = \sum_{x \in T} f(x)\)。为了保险，可以再设计一个平方和的哈希：\(G'(T) = \sum_{x \in T} f^{2}(x)\)。
（1 和 2 实际上可以看作一个哈希：都是集合到整数的映射。）
一个错误示范：
1 和 2 中的两个整数哈希函数 \(f(x)\) 可以是不同的。1 中 \(x\) 的值域为 \(1 \sim n\)，我们可以先用 mt19937_64 给 \(1 \sim n\) 中的所有整数赋一个随机的权值，作为 \(f(x)\)。2 中 \(x\) 的值域太大，不能预处理，可以用 xor shift 实现哈希：
u64 Hash(u64 x)
{
x ^= mask, x ^= x << 13, x ^= x >> 7, x ^= mask;
return x;
}
其中 mask 是一个随机的常数，而左移右移的位数和次数是随便选的。
注：集合的哈希函数用 xor sum 似乎错误率更高，不知道为什么，参见这个提交。
好吧我知道为什么了，我怎么这么蠢
标签：int,题解,sum,u64,pos,NOI2024,哈希,集合,D1T1 From： https://www.cnblogs.com/dengstar/p/18490128