问题分析

本题是一道结合交互查询、KMP自动机和高斯消元的复杂问题，核心任务是通过有限次交互查询（Query函数）推断出一个长度为1000的01字符串。算法将问题拆解为“前缀求解”“后缀求解”“中间段高斯消元”三个阶段，利用不同的数据结构和算法高效获取字符串各位置的取值。

核心概念与交互查询

1. 交互查询函数Query

题目提供的Query(m, a, b)函数是核心工具，其输入为：

• m：状态机的状态数（a和b数组长度均为m）。
• a、b：状态转移数组，a[s]表示输入为0时从状态s转移到的状态，b[s]表示输入为1时的转移状态。
• 返回值：模拟目标01字符串在该状态机上运行的最终终止状态。

算法的核心思路是：设计特定的状态机（a和b数组），通过Query的返回结果反推目标字符串的部分或整体取值。

算法思路

阶段1：求解前缀（前100位，ans[0]~ans[99]）

通过设计“链状+分支”状态机，判断前i位是否为全0，从而确定ans[i]的取值。

1.1 状态机设计（以求解ans[i]为例）

• 状态数m = i + 3，a和b数组构建逻辑：
  • 前i个状态（1~i）：构建“自环链”，若输入为0则沿链前进（a[j] = j+1），输入为1则停滞（b[j] = j）。
  • 分支状态（i+1和i+2）：
    • a[i+1] = i+2（输入0从i+1到i+2），a[i+2] = i+2（i+2为0的终止态）。
    • b[i+1] = i+1（输入1在i+1停滞），b[i+2] = i+2（i+2为1的终止态）。
• 结果判断：
  • 若Query返回i+2：说明前i+1位全为0，故ans[i] = 0。
  • 否则：前i+1位存在1，故ans[i] = 1。

1.2 遍历求解

循环i从0到99，每次设计上述状态机，通过Query结果填充ans[0]~ans[99]。

阶段2：求解后缀（后101位，ans[899]~ans[999]）

利用KMP自动机的前缀函数（nxt数组），设计状态机反推后缀的取值，采用“从短到长”的递推策略。

2.1 KMP前缀函数（nxt数组）

• suffix：存储当前已推断出的后缀子串（初始为空）。
• nxt[i]：suffix[0..i]的最长相等前后缀长度，用于优化状态机的转移逻辑，避免冗余状态。

2.2 状态机设计（扩展suffix时）

• 状态数m = len(suffix) + 1，a和b数组构建逻辑：
  • 初始状态0：a[0] = 1（输入0到状态1），b[0] = 0（输入1停滞）。
  • 中间状态1~len(suffix)-1：根据suffix的字符决定转移：
    • 若suffix[i+1] = '1'：输入0沿前缀函数转移（a[i+1] = a[nxt[i]+1]），输入1前进（b[i+1] = i+2）。
    • 若suffix[i+1] = '0'：输入0前进（a[i+1] = i+2），输入1沿前缀函数转移（b[i+1] = b[nxt[i]+1]）。
  • 终止状态len(suffix)：沿前缀函数转移（a[m] = a[nxt[m-1]+1]，b[m] = b[nxt[m-1]+1]）。
• 结果判断：
  • 若Query返回len(suffix)：说明新增的前缀字符为0，suffix[0] = '0'。
  • 否则：新增的前缀字符为1，suffix[0] = '1'。

2.3 递推扩展

从空suffix开始，每次在前端添加0或1（根据Query结果），循环101次，最终得到ans[899]~ans[999]（suffix的逆序即为后缀取值）。

阶段3：求解中间段（ans[100]~ans[898]）

中间段共799位，无法通过直接查询获取，故构建线性方程组，利用高斯消元求解。

3.1 构建线性方程（模2）

核心思想：对每个质数或小整数p，利用“周期性质”构建方程，方程的未知数为ans[100]~ans[898]，系数和常数项由前缀、后缀的取值及Query结果确定。

3.1.1 状态机设计（以p和余数d为例）

• 状态数m = 2p，分为两组状态（0~p-1和p~2p-1），a和b数组构建逻辑：
  • 非目标余数i ≠ d：a[i] = (i+1)%p（0组自环），a[i+p] = (i+1)%p + p（1组自环）；b与a相同（输入0和1转移一致）。
  • 目标余数i = d：a[d] = d + p（0组到1组），a[d+p] = d（1组到0组）；b与a相同（输入0和1交换两组状态）。
• 方程构建：
  • 设S = {i | 0≤i≤99 或 899≤i≤999 且 i%p = d}（前缀、后缀中余数为d的位置），C = XOR(ans[i] for i in S)（常数项，模2）。
  • 设T = {100≤i≤898 且 i%p = d}（中间段中余数为d的位置），方程为XOR(ans[i] for i in T) = myQuery(d,p) XOR C（模2），其中myQuery(d,p)是Query返回值是否≥p（1或0）。

3.2 高斯消元（模2）

• 用bitset<799>存储每个方程的系数（bs[i][j] = 1表示第i个方程中ans[100+j]的系数为1），val[i]存储常数项。
• 消元步骤：
  1. 按列（未知数）遍历，找到该列系数为1的方程作为主元行，交换到当前行。
  2. 用主元行消去其他行的该列系数（异或操作），同时更新常数项。
• 求解：消元后，每个方程对应一个未知数的解，直接填充ans[100]~ans[898]。

最终结果

将ans[0]~ans[999]拼接为字符串，即为目标01字符串。

代码解析

核心逻辑总结

算法的关键在于分阶段拆解问题：

1. 前缀和后缀通过“针对性状态机+直接查询”获取，利用了短序列的可直接验证性。
2. 中间段通过“周期性质+线性方程组+高斯消元”求解，解决了长序列无法直接查询的问题。
3. 全程围绕Query函数设计状态机，将“字符串取值”转化为“状态机终止状态”的判断，高效利用交互接口获取信息。