Official

B - Adjacent Replace Editorial by toam


数列は 0-indexed とします.

まず,\(A=(2^0,2^1,2^2,\ldots,2^{N-1})\) のときに作れる数を考えます.明らかに \(2^N\) 未満です.

実は,\(2^N\) 未満の非負整数のうち \(2^0\oplus 2^2\oplus 2^4\oplus\ldots\)\(2^1\oplus 2^3\oplus 2^5\oplus\ldots\) 以外の数を作ることができます.


(証明)

作る数 \(K\)\(2\) 進数で表した長さ \(N\) の 01 列を \(s\) とします(\(K=\sum_{i=0}^{N-1} s_i2^i\)).

[1] \(s_i=s_{i+1}=0\) となる \(i\) が存在するとき

最初に \(i\)\(2\) 回操作することで \(A_i=A_{i+1}=0\) とします.まず,\(i\) より左側にあって \(s_j=1\) となるようなものをすべて \(i+1\) に集めることを目指します.すなわち,\(A_{i+1}=\sum_{j=0}^{i-1}s_j2^j\) となるように操作します.これは \(j\) の降順に見ていったとき,以下のように操作すればよいです.

  • \(s_j=0\) ならなにもしない.
  • \(s_j=1\) なら \(A_{j+1},A_{j+2},\ldots,A_i\) がすべて \(0\) になるように \(j+1,j+1,j+2,j+2,\ldots,i-1,i-1\) と操作したうえで,\(j,j+1,\ldots,i\) と操作することで \(A_{i+1}\leftarrow A_{i+1}\oplus A_j(=A_{i+1}\oplus 2^j)\) とする.

同様のことを \(i+1\) の右側に対しても行います.まず,作った \(A_{i+1}\) を適当な操作によって \(A_0\) に移動します.その後,上と同じことをすることで \(i+1\) の右側にあるものをすべて \(A_0\) に移動することができます.これで \(A_0=K\) とすることができました.

[2] \(s_i=s_{i+1}=1\) となる \(i\) が存在するとき

  • \(s_{i+2}=1\) のとき
    \(i,i+1\) と操作することで \(A_{i+2}\leftarrow A_i\oplus A_{i+1}\oplus A_{i+2}\) とすることができ,\(s_i=s_{i+1}=0\) に帰着します.

  • \(s_{i+2}=0\) のとき
    \(i\) と操作することで \(A_{i}\leftarrow A_i\oplus A_{i+1}\) とすることができ,\(s_{i+1}=s_{i+2}=0\) に帰着します.

\(i+2=N\) のときは,\(i-1,i,i+1\) に対して同様のことをします.)

[3] 上記以外のとき

\(s\)010101... または 101010... のいずれかです.初手でどのように操作を行っても \(K\) に含まれる bit と含まれない bit が常に共存することになるので不可能です.


以上より,\(A=(2^0,2^1,2^2,\ldots,2^{N-1})\) の場合が解けました.操作回数は \(O(N^2)\) 回であり,操作回数上限に余裕をもって操作できます.

\(A\) が一般の場合,次の集合 \(S\subset \lbrace0,1,\ldots,N-1\rbrace\) が存在するか分かればよいです.

  • \(\displaystyle\bigoplus_{i\in S}A_i=K\)
  • \(S\neq \lbrace 0,2,4,\ldots\rbrace\wedge S\neq \lbrace 1,3,5,\ldots\rbrace\)

\(2\) つ目の条件が無かった場合は,このような \(S\) は掃き出し法で求められます.

\(2\) つ目の条件を考慮する場合の求め方について,例えば以下の \(2\) 通りがあります.

  1. \(j\in S\land j+1\in S\) または \(j\notin S\land j+1\notin S\) を満たすような \(j\) が必ず存在するため,そのような \(j\) をすべて決め打って調べればよいです.計算量は \(O(N^2\log(\max A))\) です.
  2. まず \(2\) つ目の条件を一旦無視して,XOR が \(K\) になる \(S'\) を一つ見つけます.これが \(2\) つ目の条件を満たせばそれで ok です.そうでないとき,解空間のベクトルを選んで \(S'\) との XOR を取ることを高々 \(2\) 個試せば \(2\) つ目の条件を満たす \(S\) が見つけられます.計算量は \(O(N\log(\max A))\) です.
def find(N, K, A):
    no_base = [0]
    base = []

    def calc(v):
        bit = 0
        for x, y in base:
            if v ^ x < v:
                v ^= x
                bit ^= y
        return (v, bit)

    for i in range(N):
        v, bit = calc(A[i])
        if v > 0:
            base.append((v, bit ^ (1 << i)))
        else:
            no_base.append(bit ^ (1 << i))

    v, bit1 = calc(K)
    if v != 0:
        return []

    ng0, ng1 = sum(1 << i for i in range(0, N, 2)), sum(1 << i for i in range(1, N, 2))
    for bit2 in no_base:
        bit = bit1 ^ bit2
        if bit not in [ng0, ng1]:
            return [(bit >> i) & 1 for i in range(N)]
    return []


def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    S = find(N, K, A)
    if len(S) == 0:
        return print("No")
    p = -1
    for i in range(N - 2, -1, -1):
        if S[i] == S[i + 1]:
            p = i

    if S[p] == S[p + 1] == 0:
        op = [p, p]
    else:
        if p != N - 2:
            if S[p + 2] == 1:
                op = [p, p + 1, p, p]
            else:
                op = [p, p + 1, p + 1]
                p += 1
        else:
            op = [p, p - 1, p - 1]
            p -= 1

    for i in range(p - 1, -1, -1):
        if S[i]:
            for j in range(i + 1, p):
                op += [j, j, j - 1]
            op += [p - 1, p]
    for i in range(p - 1, -1, -1):
        op += [i, i, i + 1, i]
    for i in range(p + 2, N):
        if S[i]:
            for j in range(i - 2, 0, -1):
                op += [j, j, j + 1]
            op += [1, 0]

    print("Yes")
    print(len(op))
    print(*[i + 1 for i in op])


T = int(input())
for _ in range(T):
    solve()

posted:
last update: