Long Binary String

题意翻译

现有一个无穷大的 $01$ 序列，初始全为 $0$。给定一个有限的 $01$ 序列 $S$，每次操作可以将原序列一个长为 $|S|$ 的子段异或上 $S$ ，最终需要使得整个序列只有两个 $1$。 问最终字典序最大的序列的两个 $1$ 分别所处的位置。 $|S|$ $\le$ 35。

题目描述

There is a binary string $ t $ of length $ 10^{100} $ , and initally all of its bits are $ \texttt{0} $ . You are given a binary string $ s $ , and perform the following operation some times: - Select some substring of $ t $ , and replace it with its XOR with $ s $ . $ ^\dagger $ After several operations, the string $ t $ has exactly two bits $ \texttt{1} $ ; that is, there are exactly two distinct indices $ p $ and $ q $ such that the $ p $ -th and $ q $ -th bits of $ t $ are $ \texttt{1} $ , and the rest of the bits are $ \texttt{0} $ . Find the lexicographically largest $ ^\ddagger $ string $ t $ satisfying these constraints, or report that no such string exists. $ ^\dagger $ Formally, choose an index $ i $ such that $ 0 \leq i \leq 10^{100}-|s| $ . For all $ 1 \leq j \leq |s| $ , if $ s_j = \texttt{1} $ , then toggle $ t_{i+j} $ . That is, if $ t_{i+j}=\texttt{0} $ , set $ t_{i+j}=\texttt{1} $ . Otherwise if $ t_{i+j}=\texttt{1} $ , set $ t_{i+j}=\texttt{0} $ . $ ^\ddagger $ A binary string $ a $ is lexicographically larger than a binary string $ b $ of the same length if in the first position where $ a $ and $ b $ differ, the string $ a $ has a bit $ \texttt{1} $ and the corresponding bit in $ b $ is $ \texttt{0} $ .

输入输出格式

输入格式

The only line of each test contains a single binary string $ s $ ( $ 1 \leq |s| \leq 35 $ ).

输出格式

If no string $ t $ exists as described in the statement, output -1. Otherwise, output the integers $ p $ and $ q $ ( $ 1 \leq p < q \leq 10^{100} $ ) such that the $ p $ -th and $ q $ -th bits of the lexicographically maximal $ t $ are $ \texttt{1} $ .

输入输出样例

输入样例 #1

1

输出样例 #1

1 2

输入样例 #2

001

输出样例 #2

3 4

输入样例 #3

1111

输出样例 #3

1 5

输入样例 #4

00000

输出样例 #4

-1

输入样例 #5

00000111110000011111000001111101010

输出样例 #5

6 37452687

说明

In the first test, you can perform the following operations. $ $\texttt{00000}\ldots \to \color{red}{\texttt{1}}\texttt{0000}\ldots \to \texttt{1}\color{red}{\texttt{1}}\texttt{000}\ldots $ $ </p><p>In the second test, you can perform the following operations. $ $ \texttt{00000}\ldots \to \color{red}{\texttt{001}}\texttt{00}\ldots \to \texttt{0}\color{red}{\texttt{011}}\texttt{0}\ldots $ $ </p><p>In the third test, you can perform the following operations. $ $ \texttt{00000}\ldots \to \color{red}{\texttt{1111}}\texttt{0}\ldots \to \texttt{1}\color{red}{\texttt{0001}}\ldots $ $ </p><p>It can be proven that these strings $ t $ are the lexicographically largest ones.</p><p>In the fourth test, you can't make a single bit $ \\texttt{1}$, so it is impossible.

题目大意：
存在一个长度为 \(10^{100}\) 的二进制字符串 \(t\)，最初所有位都是 \(0\)。给定一个二进制字符串 \(s\)，执行以下操作：

- 选择 \(t\) 的一个子串，并将其与 \(s\) 进行异或操作替换。
- 最终 \(t\) 有且仅有两个位是 \(1\)，即恰好有两个不同的索引 \(p\) 和 \(q\)，使得 \(t\) 的 \(p\) 和 \(q\) 位置的位是 \(1\)，其余位是 \(0\)。
- 找到满足这些条件的字典序最大的 \(t\) 或报告不存在这样的字符串。

输入输出数据格式：
- 输入格式：每行包含一个二进制字符串 \(s\)（\(1 \leq |s| \leq 35\)）。
- 输出格式：如果不存在这样的字符串 \(t\)，输出 -1。否则，输出整数 \(p\) 和 \(q\)（\(1 \leq p < q \leq 10^{100}\)），使得字典序最大的 \(t\) 的 \(p\) 和 \(q\) 位置的位是 \(1\)。

输入输出样例：
- 输入样例 #1：`1`
输出样例 #1：`1 2`
- 输入样例 #2：`001`
输出样例 #2：`3 4`
- 输入样例 #3：`1111`
输出样例 #3：`1 5`
- 输入样例 #4：`00000`
输出样例 #4：`-1`
- 输入样例 #5：`00000111110000011111000001111101010`
输出样例 #5：`6 37452687`

说明：
- 在第一个测试中，可以通过操作得到字典序最大的 \(t\)。
- 在第二个测试中，可以通过操作得到字典序最大的 \(t\)。
- 在第三个测试中，可以通过操作得到字典序最大的 \(t\)。
- 在第四个测试中，无法使任何位变成 \(1\)，因此不可能。
- 在第五个测试中，可以通过操作得到字典序最大的 \(t\)。题目大意： 存在一个长度为 \(10^{100}\) 的二进制字符串 \(t\)，最初所有位都是 \(0\)。给定一个二进制字符串 \(s\)，执行以下操作： - 选择 \(t\) 的一个子串，并将其与 \(s\) 进行异或操作替换。 - 最终 \(t\) 有且仅有两个位是 \(1\)，即恰好有两个不同的索引 \(p\) 和 \(q\)，使得 \(t\) 的 \(p\) 和 \(q\) 位置的位是 \(1\)，其余位是 \(0\)。 - 找到满足这些条件的字典序最大的 \(t\) 或报告不存在这样的字符串。 输入输出数据格式： - 输入格式：每行包含一个二进制字符串 \(s\)（\(1 \leq |s| \leq 35\)）。 - 输出格式：如果不存在这样的字符串 \(t\)，输出 -1。否则，输出整数 \(p\) 和 \(q\)（\(1 \leq p < q \leq 10^{100}\)），使得字典序最大的 \(t\) 的 \(p\) 和 \(q\) 位置的位是 \(1\)。 输入输出样例： - 输入样例 #1：`1` 输出样例 #1：`1 2` - 输入样例 #2：`001` 输出样例 #2：`3 4` - 输入样例 #3：`1111` 输出样例 #3：`1 5` - 输入样例 #4：`00000` 输出样例 #4：`-1` - 输入样例 #5：`00000111110000011111000001111101010` 输出样例 #5：`6 37452687` 说明： - 在第一个测试中，可以通过操作得到字典序最大的 \(t\)。 - 在第二个测试中，可以通过操作得到字典序最大的 \(t\)。 - 在第三个测试中，可以通过操作得到字典序最大的 \(t\)。 - 在第四个测试中，无法使任何位变成 \(1\)，因此不可能。 - 在第五个测试中，可以通过操作得到字典序最大的 \(t\)。