简要题意

给定包含 $N$ 个长度为 $M$ 的 01 串的集合 $S$，有 $Q$ 组询问，每个询问给出一个长度为 $M$ 的 01 串 $t_i$，求集合 $$\left\{u\in \mathbb{Z}_2^M\left|\exists T\subseteq S,\ \mathrm{s.t.}\ u = t_i \oplus \bigoplus_{v\in T} v\right.\right\}$$ 中，对应位为 $1$ 的下标序列的字典序最小的 01 串。

$1\le N, M, k\le 2000$

题解

字典序

处理最小化字典序问题，一个经典思路是按位贪心。在本题中，由于需要最小化的串长不固定，故贪心思路为：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应使第一个为 $1$ 的下标尽可能小。
• 在确定第一个 $1$ 的下标后，检查是否可以将后缀全部变成 $0$，如果可以则输出；否则，应使第二个为 $1$ 的下标尽可能小。
• $\ldots$

上述贪心等价于：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应尽量使第 1 位为 $1$。
• 如果确定第 1 位后，从第 2 位起可以为全零，则输出；否则，应尽量使第 12 位为 $1$。
• $\ldots$

我会线性基

因为涉及到异或，不难想到用线性基来处理本题。假设我们已经将 $S$ 处理成了相应的基向量。

对于每个询问，首先把所有主元清零，使得询问串最多只有自由元的位置非零。如果此时询问串变成全零串，则答案即为全零串。

否则，按主元顺序处理每个基向量。需要再次异或上一个基向量，当且仅当异或可以使询问串主元对应位置变成 $1$（也即此时询问串主元位置为 $0$）。特别地，如果异或完，主元位置之后变成全零，则答案即为当前串。

使用 bitset 处理，复杂度即为 $O(NMQ/w)$, 其中 $w$ 表示 bitset 位长。

除上述做法以外，还有各种使用线性基的处理方式，在此不详细展开。

不推荐考场实现的做法（简要版）

得到线性基之后，可以考虑补充没有主元对应的标准基，这样可以得到 $\mathbb{Z}_2^M$ 的一组基 $B$。将询问在 $B$ 下分解，则答案为全零串当且仅当补充的标准基的系数为 $0$。

检查完一个 $S$ 的主元位置 $x$ 后，如果这一位之后没有非零自由元，则输出当前串；否则，为了在子空间 $\mathbb{Z}_2^{M-x}$ 中处理询问串的后 $(M-x)$ 位，需要将 $x$ 对应的基向量（去掉主元的 $1$ 之后）在该子空间中重新分解，更新系数。

English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。

English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。

简要题意

对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，称长度为 $n$ 的 01 字符串 $t$ 是好的当且仅当 $\forall 1 \le i,j \le n, \exists k \in \{1,2,3\}, s_{k,i} = t_i, s_{k,j} = t_j$。设 $f(s_1,s_2,s_3)$ 为这样的好的串的数量。

现在我们有三个长度为 $n$ 的随机 01 字符串 $s_1,s_2,s_3$，其中 $s_i (1 \le i \le 3)$ 的第 $j (1 \le j \le n)$ 个字符有 $\frac{p_{i,j}}{9}$ 的概率为 1，$\left(1 - \frac{p_{i,j}}{9}\right)$ 的概率为 0，其中 $p_{i,j}$ 是一个 $0$ 至 $9$ 的整数。所有的随机事件是独立的。你需要求 $f(s_1,s_2,s_3)$ 的期望，对 $998244353$ 取模。

$n \le 3 \times 10^5$

解法

引理：设 $\text{maj}(a,b,c)$ 为 $a,b,c$ 中的众数；对于三个长度为 $n$ 的 01 字符串 $s_1,s_2,s_3$，设 $\text{maj}(s_1,s_2,s_3)$ 为长度为 $n$ 的字符串 $t$，其中 $t_i = \text{maj}(s_{1,i},s_{2,i},s_{3,i})$，则 $f(s_1,s_2,s_3) = |\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}|$。

我们首先说明以上四个字符串均满足题设条件。$s_1,s_2,s_3$ 满足条件是显然的。

对于 $t=\text{maj}(s_1,s_2,s_3)$，对于任意 $1 \le i < j \le n$，存在下标 $1 \le a < b \le 3$ 满足 $s_{a,i} = s_{b,i} = t_i$，又存在 $1 \le c < d \le 3$ 满足 $s_{c,j} = s_{d,j} = t_j$。根据抽屉原理 $\{a,b,c,d\}$ 中有两个数相等，对应的下标即是满足题设条件的 $k$。

接下来我们说明不存在其它字符串满足条件。当满足条件的字符串 $t$ 不等于 $\text{maj}(s_1,s_2,s_3)$ 时，设 $t_i \ne \text{maj}(s_1,s_2,s_3)_i$，则 $t_i$ 只在 $s_{1,i},s_{2,i},s_{3,i}$ 中出现恰好一次（不能不出现，否则不可能满足题设条件），不妨假设其为 $s_{1,i}$。此时取任意 $j \ne i$，根据题设条件必然有 $t_j = s_{1,j}$（因为 $k$ 必须取 $1$），因此 $t = s_1$。

进一步地，可以分类讨论得到 $|\{s_1,s_2,s_3,\text{maj}(s_1,s_2,s_3)\}| = 4 - \sum_{i=1}^3 [\text{maj}(s_1,s_2,s_3) = s_i]$：

• $f(s_1,s_2,s_3) = 4$ 时四个字符串两两不同；
• $f(s_1,s_2,s_3) = 3$ 时必然是某个 $s_i = \text{maj}(s_1,s_2,s_3)$ 的情况而不是 $s_i = s_j$ 的情况，因为 $s_i = s_j$ 会直接导致 $\text{maj}(s_1,s_2,s_3) = s_i$；
• $f(s_1,s_2,s_3) = 2$ 时必然是 $s_i = s_j = \text{maj}(s_1,s_2,s_3)$ 且剩余的字符串跟它们不同的情况；
• $f(s_1,s_2,s_3) = 1$ 时必然是四个字符串相等的情况。

由于期望的线性性，只需要计算 $\Pr[\text{maj}(s_1,s_2,s_3) = s_i]$ 即可。由于每一位的随机事件是独立的，所以直接把每一位相等的概率乘起来就行了。

复杂度 $O(n)$。

题外话

• 本题中文名“石墨烯”纯属出题人夹带私货，与题目无关，具体含义不便透露，大家不要过度解读。
• 本题原来只有 $k=0$ 这个版本作为签到，但是因为某些原因需要稍微加强难度，就变成了现在这个版本。

Description

• 给定长为 $n$ 的序列 $a, b$，每轮操作先使每对 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差，然后使 $a$ 循环右移一位。
• 操作开始前，可以先对 $a$ 进行 $k$ 次 $a_i \leftarrow a_{i-1}$（需保证 $a_i$ 恒非负），问最少几轮操作才能使 $a$ 全变为零？
• $1 \le n, \sum{n} \le 5 \times 10^5$，$1 \le a_i, b_i \le 10^9$。

$k=0$

• 考虑对于每个 $a_i$ 分别求出至少循环右移几次之后会变为零，记之为 $d_i$，则答案即为 $\max_{1≤\le i \le n}{d_i}$。
• 遇到环上问题，首先考虑断环为链（即令 $a_{i+n}=a_i,b_{i+n}=b_i$）。

• 考虑如下转化：记 $s$ 为由 $a_1$ 个左括号，$b_1$ 个右括号，$a_2$ 个左括号，$b_2$ 个右括号，……，$a_{2n}$ 个左括号，$b_{2n}$ 个右括号顺次拼接而成的括号串，则原题中的操作过程就相当于对 $s$ 进行括号匹配的过程，而 $a_i$ 会被哪个 $b_j$ 首次消成零，就取决于 $a_i$ 对应的第一个左括号所匹配的右括号属于哪个 $b_j$ 。

  • “使 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差” $\rightarrow$ “匹配 $a_i, b_i$ 对应的括号”；
  • “使 $a$ 循环右移一位” $\rightarrow$ “未被匹配的左括号继续向右寻找右括号尝试匹配”。
• 对于括号匹配问题，自然想到利用前缀和转化。
• 令 $c_i=\sum_{j=1}^{i}(a_i-b_j)$，记 $p_i$ 为最小的满足 $p_i > i$ 且 $c_{p_i} \le c_i$ 的下标，则 $d_i$ 即为 $p_i-i$。
• 使用单调栈即可求出所有 $p_i$，时间复杂度为 $O(\sum n)$。

正解

• 加入了 $k$ 的限制后，考虑二分答案 $x$，转而求在 $x$ 轮操作后将 $a$ 全变为零的最少 $-1$ 次数。
• 发现直接在断环为链的 $2n$ 个数上不太好计算贡献（因为可能会重复计算），所以我们进行如下调整：将 $a,b$ 同时循环右移若干位，使得 $a_i-b_i$ 的前缀和 $c_i$ 的最小值在 $c_n$ 处取到。
• 这样调整的好处是，对于调整后的 $a,b$，我们所关心的 $p_i(1 \le i \le n)$ 都不会超过 $n$，也就是说，在实际操作过程中，不会出现 $a_n > 0$ 右移到 $a_1$ 的情况。
• 因此，我们仅通过调整 $a, b$ 就将环上问题转化为了一个长为 $n$ 的链上问题。
• 接下来考虑如何在调整后的 $a,b$ 上计算答案为 $x$ 时的最少 $-1$ 次数。
• 不难想到对 $a$ 从 $n-x$ 到 $0$ 使用贪心，若当前位置 $i$ 对应的 $d_i=p_i-i > x$，即若 $\min_{j=i+1}^{i+x}{c_j} > c_i$，则对 $a_{i+1}$ 进行 $\min_{j=i+1}^{i+x}{c_j} - c_i$ 次 $-1$。
• 整个过程均可通过单调栈维护。
• 时间复杂度为 $O(\sum n \log k)$。

English version

Each operation transform three adjacent characters into one. If the string starts with 11, the answer should be yes since we can first transform the remaining part into a single 0 or 1 and then the value of 11? is always $1$.

If the string ends with 1, only 101 has no solution, otherwise it starts with 11 or 0, or we can transform 10? in the front of the string into a 0. Then transform the rest part of the string into a single character to make the last operation 0?(anything):1 makes 1.

If an operation transformed a string ending with 0 into one ending with 1, it must be 1?1:0 makes 1.

Consider the case where the strings contains 11 as a substring. After transforming the remaining part, ?11?? or ??11? will be derived. The cases are 01100, 00110, 01110, 10110. All other cases start with 11 or end with 1.

All cases of ??11? have a solution:

(0?0:1)?1:0 makes 1.

(0?1:1)?1:0 makes 1.

1?(0?1:1):0 makes 1.

However, 01100 has no solution.

Since 0?0:1 equals 1, before the last 1, any two adjacent 0's with no 1 in between can be eliminated. Thus, if there are two 1's with an even number of 0's in between, and there are an even number of characters in front the former 1, i.e., (..)*1(00)*1(..)*0 in regular expression, the answer should be yes, since after eliminating the 0's in between, the 1's become adjacent. The parity of the characters before the former 1 guarantees that it will not become 01100.

Another case is that the string ends with 0 and every pair of adjacent 1's has an odd number of 0's in between. Since 0(1?0:1)0 makes 000, 1(0?1:0)1 makes 101, 10(1?0:0)01 makes 10001, there is no way to change the parity of the consecutive 0's to make 11 to change the ending 0 into 1.

In the remaining case, there are even 0's between some pair of adjacent 1's, but the number of characters before the first 1 is odd, there must be only one pair. Suppose the string is 1-indexed. It is because the indices of such pair of 1's must be [odd, even]; while the indices in the previous case must be [even, odd]. Thus, if there are two such pairs of this case [odd, even], in the parity sequence [odd, even, ..., odd, even] there must be an [even, odd] as a substring.

Therefore, any other pair of adjacent 1's must have odd 0's in between, i.e., $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{black}(00)^*\color{red}1\color{blue}((00)^*01)^*\color{black}(00)^+$ in regular expression. Any operation remains the string in this case, except that the string is $0(00)^*\color{blue}(10(00)^*)^*\color{red}1\color{red}1\color{black}(00)^+$ and the operation is $\color{red}1\color{black}?\color{red}1\color{black}:0$ makes 1. Since it must ends with `00`, it becomes a string ending with `0` and every pair of adjacent 1's has odd 0's in between, which is a case mentioned before that has no solution.

In conclusion, it has a solution if and only of at least one of the two following conditions is met:

• It ends with 1 but it is not 101.
• It has two adjacent 1's such that there are even 0's in between and the number of characters before the former 1 is even.

中文版本

英文题解里描述了做本题的一种思路，以及证明。

如果要直接写做法的话，是下面这样：

假设字符串下标从 $1$ 开始编号。

首先判断是否存在 $i,j$ 使得 $i$ 是奇数，$j$ 是偶数，$s_i$ 和 $s_j$ 都是 1，且这两个字符中间都是 0。

• 如果是，那么先把中间的 0 和 $s_j$ 写成 (0?0:0?0:.....:1)，表达式的值为 1（一定有偶数个 0），然后分三种情况：

  • 如果 $i=1$，那么就直接把 $s_j$ 后面的部分变成一个数，最后变成 (1?1:*) 是 1。

  • 否则考虑把 $s$ 的第 $1\sim i-2$ 位变成一个数，并计算出这个值。

    • 如果值为 0 那么有 ((0?*:1)?1:*) 等于 1。
    • 如果值为 1 那么有 (1?(*?1:1):*) 等于 1。

• 否则，判断是否满足字符串末尾是 1 且本身不等于 101：

  • 如果是，那么字符串一定以 0 或 10 开头，于是第一位或前三位操作后一定是 0，然后留下开头的 0 和结尾的 1，把中间的部分变成一个数，最后 (0?*:1) 结果一定是 1。
  • 否则，无解。

此外，还有一种比较特别的解法：

可以发现构造的过程中需要用到不超过两层括号（不算整个表达式最外面一层）。所以如果你要是猜到了这一点可以直接使用动态规划从右到左扫这个字符串，记录每一层栈中的内容。最多三层栈，每层栈最多两个比特，一共 $6^3+6^2+6=258$ 种状态。大概也能过。

不知道有没有什么奇怪的乱搞可以搜过去。不过我还是欢迎吧。