类似的题：qoj6668，CF1705F。
首先你发现你确定这个序列至少需要两次询问，因为 01 互换是等价的方案，这一点将不会在后文赘述。
询问本质及其可以求出的信息：
考虑询问一个子集 $S$ 你能得到的结果为 $a$，我们设 $0$ 的数量为 $x$，$1$ 的数量为 $y$，则会有以下等式：
$x \times y = a$。
$x + y = |S|$。
此时你已知的是 $a,|S|$，显然此时你可以求出 $x,y$ 的值。
注意，若你只看一次询问，那么你能得到的情况是两种情况之一：
$0$ 的数量为 $x$，$1$ 的数量为 $y$。
$0$ 的数量为 $y$，$1$ 的数量为 $x$。
首先 $n \le 3$，直接暴力询问即可，在此不再赘述。
考虑 $n > 3$ 的情况，根据鸽巢原理，前 $3$ 个数字必定有至少两个 $0$ 或两个 $1$。
我们考虑这两个相同的数字能让我们干啥，在这里我们假设这两个相同的数字为 $0$。
考虑增量法，我们每次随机添加两个没确定的数字时会出现哪些情况：
$S=\{0,0,0,0\}$，此时交互库返回的结果为 $0$。
$S=\{0,0,0,1\}$，此时交互库返回的结果为 $3$。
$S=\{0,0,1,0\}$，此时交互库返回的结果为 $3$。
$S=\{0,0,1,1\}$，此时交互库返回的结果为 $4$。
容易观察到，除了第 $2,3$ 种情况，其余两种情况我们均可以求出枚举的这两个数字的值。
那么我们容易发现第 $1,4$ 种情况可以确定 $2$ 个数字。
考虑出现第 $2,3$ 种情况我们可以得到什么信息，观察到这两种情况新加入的两个数字都不同，那么显然我们知道这两个数字中的一个就可以求出另一个数字的值，写一个并查集维护即可，可以确定 $1$ 个数字。
那么综合可得每次期望可以问出 $\displaystyle\frac{3}{2}$ 个数字，期望询问次数为 $\displaystyle\frac{2}{3} n$ 次，通常情况下跑不到 $\ge 700$ 次，可以获得 $50$ 分。
算法 2：
这部分看不懂可以看另一篇题解。
首先我们钦定 $s_1 = 0$（若事实上 $s_1 = 1$ 时我们视为所有 01 数位均翻转），然后我们考虑我们考虑把原操作转化为询问一个子集内 $0,1$ 的具体个数是多少，容易发现原操作做 $2$ 次即可求出这个子集的 01 两个数字的具体出现次数，具体的，设 $T = \{i \ |\ i \in S \lor i = 1\}$，则我们需要求出 $S$ 中的 01 数量可以第一次询问 $S$，第二次询问 $T$，通过解方程即可求出 $S$ 中的 01 两个数字的具体出现次数（注意，这里的 $S$ 中肯定不含有 $1$，因为我们已经顷定了 $s_1 = 0$，因此此时我们可以通过这两个询问结果来解方程解出 $0,1$ 两种数字分别出现的次数）。
那么我们就将原来的询问转化成了可以询问一个子集，交互库会给出这个子集中 $0$ 的个数（$1$ 的个数通过计算不难求出）。
仍然考虑增量法，设 $f_i$ 为增量 $i$ 次所需要的总询问次数（不包括给出答案），$g_i$ 为增量 $i$ 次可以求出序列中的数字总数量。
设 $Q_{i,j}$ 增量 $i$ 次的所需要的询问集合的第 $j$ 个询问。
为了更好表示，我们画一张图，下图中，划分为了 $3$ 个区间 $A,B,C$。
$Q_{A,j}$ 表示区间 $A$ 集合所需要的询问集合，$Q_{B,j}$ 表示区间 $B$ 集合所需要的询问集合，$c_j$ 表示区间 $C$ 的第 $j$ 个数字。
对于一个 $j$，$a$ 表示 $Q_{A,j}$ 的询问集合的 $1$ 的数量，$b$ 表示 $Q_{B,j}$ 的询问集合的 $1$ 的数量，$c$ 表示 $c_j$ 的值。
三个区间集合拼接起来即为所有询问。
按照如图方式询问即可，根据递推可知：
$f_{0 \sim 8} = \{0,2,6,14,30,62,126,254,510\}$。
$g_{0 \sim 8} = \{1,2,5,13,33,81,193,449,1025\}$。
则最终询问次数为 $510+2+2=514$ 次，前面 $2$ 次为查询最终 $B$ 区间 $1$ 的数量的所需询问次数，后面 $2$ 次为给出答案的次数。
可以获得 $76$ 分。
算法 3：
我们考虑在算法 $2$ 的基础上再凹一下次数。
根据鸽巢原理，长度为 $x$ 的前缀至少有 $\lfloor\displaystyle\frac{n+1}{2}\rfloor$ 个 $0$ 或 $1$。
设 $len_i$ 为前 $i$ 个字符 $0$ 的数量和 $1$ 的数量的最大值。
仍然考虑增量法。若此时你知道了前 $i$ 个数字的值，那么显然我们可以增加 $len_i$ 个数字，此时若想要知道新增的 $len_i$ 个数的 0 的数量，则只需要 $1$ 次询问即可。具体的，只需要取前 $i$ 个数的出现次数多的次数的数字和新增加的 $len_i$ 个数字的一个子集询问即可。
视实现情况询问次数在 $420$ 次左右，可以获得 $89$ 分左右的分数。
算法 4：
仍然钦定 $s_1 = 0$。
考虑优化算法 3。
我们设 $f_n$ 表示序列长度为 $n$ 所需要的最少询问次数，$g_n$ 表示此时你知道了至少 $n$ 个 $0$ 或 $n$ 个 $1$ 再询问 $n$ 个你此时不知道的数字所需要的最少询问次数。
考虑刻画算法 2 的操作。
设做一次操作前的序列长度为 $x$。
- $+1$，表示通过 $1$ 次询问来知道 $1$ 个新的数字。
- $\times 2 + |Q|$，表示通过 $|Q| \times 2$ 次询问来知道 $x + |Q|$ 个新的数字。
可以跑一遍最短路来找出只考虑这两种操作的最优解。
询问次数为 $385$ 次，可以获得 $95$ 分。
算法 5：
考虑优化算法 4。
我们在原来的刻画操作的基础上再增加一种操作。
设做一次操作前的序列长度为 $x$。
- $+1$，表示通过 $1$ 次询问来知道 $1$ 个新的数字。
- $\times 2 + |Q|$，表示通过 $|Q| \times 2$ 次询问来知道 $x + |Q|$ 个新的数字。
- $\times 3 + 2|Q|$，表示通过 $|Q| \times 3$ 次询问来知道 $2x + 2|Q|$ 个新的数字。
可以跑一遍最短路来找出这三种操作的最优解，可以比原来少 $1$ 次询问。
事实上，新增的这个操作可以看成是三分治。
比较容易注意到四分治，五分治……均不会使次数变得更优。
询问次数为 $384$ 次，可以获得 $100$ 分。
如果你有更优秀的做法，欢迎跟我私信交流。 好像被 ou 爆标了，不管了。