Zobrist hashに関する知識を前提としています．必要に応じて先にABC367Fの解説を参照してください．https://atcoder.jp/contests/abc367/tasks/abc367_f/editorial

一般に素数\(\,p\,\)に対して

\[(\mathbb{Z}/p\mathbb{Z})^\times\cong(\mathbb{Z}/(p-1)\mathbb{Z},+)\]

が成立します．したがって\(\,\text{mod} \,\,\,p\,\)の積をハッシュ値とすることは\(\,\text{mod}\, \,\,(p-1)\,\)の和をハッシュ値とすることに等しくなります．

\[998244353-1=2^{23}\times 7\times 17\]

であり，この約数を利用して\(\,1\,\)クエリあたりの衝突確率を上げることを想定した問題となっています．以降は\(\,p=998244353\,\)とし，ハッシュ値は乱数置換後の\(\,\text{mod}\, \,\,(p-1)\,\)の和を意味するものとします．

多重集合\(\,X\)，\(Y\,\)のハッシュ値を\(\,H(X)\)，\(H(Y)\,\)と置き，\(\,X\,\)と\(\,Y\,\)で含まれる個数の差が\(\,k(\neq 0)\,\)となる要素の\(\,1\,\)つを\(\,e\,\)と置くと，適当な\(\,C\in \mathbb{Z}/(p-1)\mathbb{Z}\,\)を用いて

\[H(X)-H(Y)=kH(\{e\})+C\quad(\text{mod} \,\,\,p-1)\]

と表せます．特に工夫が無ければ衝突確率(この値が\(0\)に一致する確率)は\(\frac{1}{p-1}\)であり，無視できる程度に小さくなります．しかし，\(\,k\,\)を適切に設定することで確率が変化します．\(p-1\,\)の約数の\(\,1\,\)つを\(\,M\,\)と置くと，乱数の割り当て方によらず

\[MH(\{e\})\in\{Mx: x\in \mathbb{Z}/(p-1)\mathbb{Z}\}=\{0,M,2M…p-1-M\}\]

が成立するので\(MH(\{e\})\)のとり得る値の個数は\(\frac{p-1}{M}\)個になります．したがって\(\,X\)，\(Y\,\)の各要素が\(\,M\,\)個ずつになっているようなクエリでは，\(H(X)-H(Y)=0\,\)となる確率は\(\frac{M}{p-1}\)になります．

数列\(\,A\)，\(B\,\)として同一要素\(\,M\,\)個ずつを\(\,K\,\)セット 並べたものを用意します．

\[A=(1,…,1,2,…,2,…,K,…,K)\]

\[B=(K+1,…,K+1,…,2K,…,2K)\]

\(A\)，\(B\,\)について各要素の含まれる個数が丁度\(M\)個ずつとなる空でない区間のとり方は\({}_{K+1}\mathrm{C}_2=\frac{K(K+1)}{2}\)通りであるので，異なるクエリを\(\frac{K^2(K+1)^2}{4}\)通り作ることができます．各クエリが独立であることを仮定すると（厳密には独立ではないが影響は十分小さい）\(\,1\,\)つのテストケースが不正解となる確率はおよそ

\[1-(1-\frac{M}{p-1})^{\frac{K^2(K+1)^2}{4}}\]

になります．\(KM+\frac{K^2(K+1)^2}{4}=N+Q\leq 10^6\,\)の制約から\(\,K\leq 45\,\)までの範囲で試せば十分です．\(K\,\)を先に決め打ち，制約の範囲に収まる中で最大の\(\,M\,\)を用いれば良いです．例えば\(\,K=39\)，\(M=8704(=\frac{p-1}{114688})\,\)とすれば，\(N+Q=314886+608400=923286\,\)であり，このとき\(\,1\,\)つのテストケースが不正解となる確率は

\[ 1-(1-\frac{1}{114688})^{608400}\fallingdotseq 0.99\]

となるので，余裕をもってACが得られます．なお，\(K\,\)や\(\,M\,\)等のパラメータの微調整に依らずにACが得られるように制約には余裕を持たせており，\(25\leq K \leq 42\)の範囲での安定したACを確認しています．

余談:\(p-1\)の約数について考慮していない提出がACとなる確率は\(10^{-100}\)を下回ります．