Codeforces Round #853 (Div. 2)

D. Serval and Shift-Shift-Shift

https://codeforces.com/contest/1789/problem/D

2 seconds / 256 megabytes

standard input / standard output

## Problem

Serval has two $n$-bit binary integer numbers $a$ and $b$. He wants to share those numbers with Toxel.

Since Toxel likes the number $b$ more, Serval decides to change $a$ into $b$ by some (possibly zero) operations. In an operation, Serval can choose any positive integer $k$ between $1$ and $n$, and change $a$ into one of the following number:

• $a\oplus(a\ll k)$
• $a\oplus(a\gg k)$

In other words, the operation moves every bit of $a$ left or right by $k$ positions, where the overflowed bits are removed, and the missing bits are padded with $0$. The bitwise XOR of the shift result and the original $a$ is assigned back to $a$.

Serval does not have much time. He wants to perform no more than $n$ operations to change $a$ into $b$. Please help him to find out an operation sequence, or determine that it is impossible to change $a$ into $b$ in at most $n$ operations. You do not need to minimize the number of operations.

In this problem, $x\oplus y$ denotes the bitwise XOR operation of $x$ and $y$. $a\ll k$ and $a\gg k$ denote the logical left shift and logical right shift.

## Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le2\cdot10^{3}$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le2\cdot10^{3}$) — the number of bits in numbers $a$ and $b$.

The second and the third line of each test case contain a binary string of length $n$, representing $a$ and $b$, respectively. The strings contain only characters 0 and 1.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^{3}$.

## Output

For each test case, if it is impossible to change $a$ into $b$ in at most $n$ operations, print a single integer $-1$.

Otherwise, in the first line, print the number of operations $m$ ($0\le m\le n$).

If $m>0$, in the second line, print $m$ integers $k_{1},k_{2},\dots,k_{m}$ representing the operations. If $1\le k_{i}\le n$, it means logical left shift $a$ by $k_{i}$ positions. If $-n\le k_{i}\le-1$, it means logical right shift $a$ by $-k_{i}$ positions.

If there are multiple solutions, print any of them.

## Example

Input

3
5
00111
11000
1
1
1
3
001
000

Output

2
3 -2
0
-1

Note

In the first test case:

The first operation changes $a$ into $\require{cancel}00111\oplus\cancel{001}11\underline{000}=11111$.

The second operation changes $a$ into $\require{cancel}11111\oplus\underline{00}111\cancel{11}=11000$.

The bits with strikethroughs are overflowed bits that are removed. The bits with underline are padded bits.

In the second test case, $a$ is already equal to $b$, so no operations are needed.

In the third test case, it can be shown that $a$ cannot be changed into $b$.

## 题解

#### 不成立的情形

\begin{align} 0\oplus bit&=bit\\ 1\oplus bit&=\neg bit \end{align}

#### 如何构造通解

$$10010\\ \quad\quad10010\\ \overline{10110}\\$$

$$10110\\ \quad\quad\quad10110\\ \overline{10100}\\$$

$$10100\\ \quad\quad\quad\quad10100\\ \overline{10101}\\$$

$$\quad\quad\quad\quad00011\\ 00011\\ \quad\quad\quad\quad\overline{10011}\\$$

$$\quad\quad\quad\quad10011\\ 10011\\ \quad\quad\quad\quad\overline{00011}\\$$

## 代码

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

vector<int> getans(string a, string b)
{
vector<int> ans;
int n = a.size();
if (a[0] == '0')
{
int t = n - 1;
while (a[t] == '0')
t--;
ans.push_back(t);
a[0] = '1';
}
for (int i = 1; i < n; i++)
{
if (a[i] != b[i])
{
ans.push_back(-i);
string t = a;
for (int j = 0; j < n; j++)
{
if (i + j >= n)
break;
if (t[j] == a[i + j])
a[i + j] = '0';
else
a[i + j] = '1';
}
}
}
if (b[0] == '0')
{
int t = n - 1;
while (a[t] == '0')
t--;
ans.push_back(t);
a[0] = '0';
}
return ans;
}

void solve()
{
int n;
cin >> n;
string a, b;
cin >> a >> b;
if (a == b)
{
cout << 0 << endl;
return;
}
if (a.find('1') == a.npos ||
b.find('1') == b.npos)
{
cout << -1 << endl;
return;
}
vector<int> ans = getans(a, b);
if (ans.size() <= n)
{
cout << ans.size() << endl;
for (auto ele : ans)
cout << ele << ' ';
cout << endl;
return;
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
ans = getans(a, b);
cout << ans.size() << endl;
for (auto ele : ans)
cout << -ele << ' ';
cout << endl;
return;
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}