[JOI Open 2023] 古代机器 2 / Ancient Machine 2 题解

传送门：[JOI Open 2023] 古代机器 2 / Ancient Machine 2
完全不会做这种交互题。
形式化题意：交互库有一个 01 串 \(s\)（下标从 \(0\) 开始），你需要通过若干次询问求出 \(s\)，每次询问，你可以构造一个大小为 \(m\) 的自动机（\(m\) 由你自己定），自动机上的状态节点从 \(0\) 到 \(m-1\) 编号，每个状态都有 \(0\) 和 \(1\) 两种转移（每个状态的两种转移由你自己定），起始状态为 \(0\)，交互库会把 \(s\) 放到这个自动机上进行计算，并返回最终到达的状态编号。要求询问次数不超过 \(1000\)，同时最小化所有询问 \(m\) 的最大值。
算法一：\(m\le 1002\)

考虑依次确定每一位，如果我现在要确定 \(s_i\)，则我们可以把状态 \(0\) 到 \(i\) 串成一条链，然后 \(i\) 的 \(0\) 转移指向 \(i+1\)，\(1\) 转移指向 \(i+2\)，最后把 \(i+1,i+2\) 连成自环，如下图：

最后只要看交互库返回的是 \(i+1\) 还是 \(i+2\) 即可，\(m_{max}=n+2\)。
期望得分 \(10pts\)。
算法二：\(m\le 502\)

相当于折半了，我们先用算法一确定前 \(500\) 位，然后考虑怎么确定后 \(500\) 位。
假设我们已经确定了长度为 \(len-1\) 的后缀，现在我们要确定倒数第 \(len\) 位，我们不妨先假设他是 1，现在相当于有一个长度为 \(len\) 的 01 串 \(t\) 要判断他是否是 \(s\) 的后缀。
直接构造 \(t\) 的 KMP 自动机即可，若当前在编号为 \(i\) 的状态代表目前 \(s\) 的后缀和 \(t\) 的前缀匹配了 \(i\) 位，最后看一下是否返回 \(len\) 即可。
后半部分的 \(m=len+1\)，期望得分 \(37pts\)。
算法三：\(m\le 114\)

考虑换一个思路，上面都是一位一位确定的，如果我们能一次知道若干个位置的异或和，那么我们就可以得到若干个线性异或方程，只要本质不用的方程足够多，我们就可以解出所有的位置。
事实上我们可以通过构造一个大小为 \(2p\) 的自动机，来求出所有满足 \(i \equiv q \pmod p\) 的 \(s_i\) 的异或和，只需要构造两个大小为 \(p\) 的环，并把 \(q\) 和 \(q+p\) 的 \(1\) 出边指向另一个环即可。
举个例子，当 \(p=5,q=2\) 时，可以如下构造：

不难发现只有在 \(i \bmod 5 = 2\) 的位置且 \(s_i=1\) 时会发生所在环的变换，所以如果最后在上面那个环就代表  \(\bmod 5 =2\) 的位置有偶数个 1，否则有奇数个 1。
最终打表得到如果要构造出 \(1000\) 个本质不同的方程 \(p\) 最大需要到 \(57\)。判断本质不同用线性基就可以了。
期望得分 \(97pts\)。
正解

事实上我们先用算法 \(1,2\) 把前后各 \(100\) 位确定下来，中间 \(800\) 位用算法 \(3\) 即可通过。
code
代码中把 \(s\) 的下标从 \(1\) 开始了。
[code]#include#define Debug puts("-------------------------")#define PII pair#define fi first#define se second using namespace std;int Query(int m, std::vector a, std::vector b);const int N=1e3+5;int n,a[N],b[N],m;int fail[N],nxt[N][2];char s[N],t[N];int query(int op){        vector A(m),B(m);        if(op) for(int i=1;i