一番左にあるカードを左から \(0\) 枚目、その右にあるカードを左から \(1\) 枚目、\(\dots\) とし、\(A_i~(1 \leq i \leq P)\) や \(B_j~(1 \leq j \leq Q)\) の値はこれに合わせて入力から \(1\) 引かれているものとします。

以下、「多項式」とは \(\mathbb{F_2} \) 係数多項式を意味します。

カードの表裏の状態を \(N-1\) 次以下の 多項式 \(f\) で表し、\(f\) の \(i\) 次の係数が \(1\) のとき左から \(i\) 枚目のカードは表を向いていて、\(0\) のとき裏を向いているものとします。

「一番右にあるカードを一番左に移動し、移動させたカードが表を向いているなら左から \(A_1, A_2, \dots, A_P\) 枚目のカードの表裏を全て反転させる」というのは、以下と等価です。

• \(f_A=1 + x^N + \sum_{i=1}^P x^{A_i}\) として、\(f\) を \(xf\bmod f_A\) で置き換える

「左から \(B_1, B_2, \dots, B_Q\) 枚目のカードの表裏を全て反転させる」というのは、以下と等価です。

• \(f_B=\sum_{j=1}^Q x^{B_j}\) として、\(f\) を \(f+f_B\) で置き換える

カードの表裏の初期状態を \(f_S\) 、操作によって達成したいカードの表裏の状態を \(f_T\) とします。

操作をちょうど \(k\) 回行う場合を考えます。

\(u_1, u_2, \dots, u_k\) を、\(i~(1 \leq i \leq k)\) 回目の操作で左から \(B_1, B_2, \dots, B_Q\) 枚目のカードの表裏を全て反転させたとき \(u_i=1\)、そうでないなら \(u_i=0\) と定めます。このとき、最終的なカードの表裏の状態は \(f = (f_S x^k + \sum_{i=1}^k u_i x^{k-i} f_B) \bmod f_A\) となります。

\(u_1, u_2, \dots, u_k\) を自由に決められるとき、\(\sum_{i=1}^k u_i x^{k-i}\) が取りうる範囲は \(k-1\) 次以下の多項式全体であることから、ちょうど \(k\) 回の操作後に \(f=f_T\) を達成できる必要十分条件は以下のように表せます。

• \(pf_A + qf_B = f_S x^k + f_T\) を満たす多項式の組 \((p, q)\) であって、\(q\) の次数が \(k-1\) 以下であるものが存在する

「\(q\) の次数が \(k-1\) 以下である」という条件を無視すると、上記の方程式の解は以下のようになります。

• \(g=\gcd(f_A, f_B)\) とする。\((f_S x^k + f_T)\) が \(g\) で割り切れない場合、解は存在しない。割り切れる場合、解は必ず存在し、解の1つを \((p', q')\) として一般解は \((p, q) = (p' + tf_B / g, q' + tf_A / g)\) （\(t\) は任意の多項式）と表せる。

よって、\((f_S x^k + f_T) \bmod g = 0\) であるか判定し、\(0\) である場合は \(p'f_A + q'f_B = f_S x^k + f_T\) を満たす \((p', q')\) を1つとり、\(q' \bmod (f_A / g)\) の次数が \(k-1\) 以下であるかを判定すればよいです。

それでは、具体的な解法を説明します。

bitset を用いて多項式を扱います。以下、ワードサイズを \(w\) とします。

\(N\) 次以下の多項式 \(f_1, f_2\) について、\(xf_1\) や \(f_1 + f_2 \) を \(O(N/w)\) で計算できます。
また、筆算の要領で計算することで、\(f_1f_2\) を \(O(N\deg(f_2)/w)\)、\(f_1\) を \(f_2\) で割った商と余りを \(O(N(\deg(f_1)-\deg(f_2))/w)\) で計算することができます。

まず、拡張ユークリッドの互助法によって、\(pf_A + qf_B = g\) の解の1つ \((p_0, q_0)\) と \(g\) を求めます。これは適切に実装することで \(O(N^2 / w)\) で計算できます。

操作回数の上限を \(M\) とします。

\(k=1, 2, \dots, M\) の順に、ちょうど \(k\) 回の操作で目標を達成できるか判定します。

\(f_k = f_S x^k + f_T\) とします。\(f_S x^{k-1} \bmod g\) から\( f_S x^k \bmod g\) を \(O(N/w)\) で計算できるため、\(f_k \bmod g\) は各 \(k\) について \(O(N/w)\) で計算できます。

\(f_k \bmod g = 0\) のとき、\(p_0f_A + q_0f_B = g\) の両辺に \(f_k / g\) をかけると \((p_0f_k/g)f_A + (q_0f_k/g)f_B = f_k\) が得られることから、\((p, q) = (p_0f_k/g, q_0f_k/g)\) は \(pf_A + qf_B = f_k\) の解の1つです。したがって、\((q_0f_k/g) \bmod (f_A/g)\) の次数が \(k-1\) 以下であるか判定できればよいです。

ここで、\((q_0f_k/g) \bmod (f_A/g) = (q_0f_k \bmod f_A) / g\) が成り立ち、次数が \(k-1\) 以下であるか判定するためには、\(\deg(q_0f_k \bmod f_A) - \deg(g) \leq k-1\) であるかを確かめればよいです。

\(f_k \bmod g\) と同様に、\(q_0f_k \bmod f_A\) は各 \(k\) について \(O(N/w)\) で計算できます。条件を満たす場合には \((q_0f_k \bmod f_A) / g\) が解であるため、実際に計算して出力すればよいです。

以上でこの問題を解くことができました。時間計算量は \(O(N(N+M)/w)\) です。