Assign a random number \(0 \leq z_i < L\) for each \(1\leq i \leq N\), where \(L\) is some large number. We can easily find, for any contiguous subsequence, the sum of \(z_{A_i}\) in such subsequences, in \(O(1)\) using prefix sums.

If the sums do not match, the answer is No. Otherwise, the answer is most probably Yes; we claim that the probability of being wrong is at most \(1/L\) per query, thus the probability of passing the test case is at least \(1 - Q/L\) (assuming the worst case that all error possibilities are mutually exclusive). Proof: consider any two multisets that do not match. This means there is at least one element whose multiplicities in the two multisets do not match. Pick an arbitrary one (perhaps the smallest) and call it \(x\). The probability that \(z_x\) just happens to be a value that would force their sums to match is at most \(1/L\). This applies even if all other \(z_i\) was chosen by an enemy, so even though it’s hard to calculate the exact probability, we know it’s not worse than \(1/L\).

Picking \(L = 2^{45}\) or \(10^{13}\) will avoid overflow, and keep the failure rate at about \(2 \cdot 10^{-8}\), which is generally acceptable.

Other ideas:

• If your programming language has support for 128-bit integers, you can use those to use a larger \(L\) and lower the failure rate even further
• You might think of just adding up random 64-bit integers and ignoring overflows. This works, but you also lose some of the probability guarantee; think of the worst case of both sequences being \(2^{17}\) instances of some integer, the lower \(17\) bits are zeroed out and useless
• Another method is to use a large prime modulus when adding up values. \(2^{61} - 1\) is convenient as it allows reduction by bit-shifting and adding.
• This is similar to a method called Zobrist hashing, which uses the xor-sum of randomized hashes to quickly compare sets. However, since we are comparing multisets rather than sets, we use addition instead of xor.