自动搬运

查看原文

来自洛谷，原作者为

	ZnPdCo 「是不是糖的都无所谓了」

搬运于2025-08-24 22:33:37，当前版本为作者最后更新于2025-08-14 22:05:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不管是 官方题解做法 还是这种做法，这道题都已经不太像紫题了，非常考验选手的注意力。做到了 $26624\ll 63000$ 次查询，尽力了。欢迎大家进一步交流，$O(1)$ 级别的优化也是可以的。

使用构造题常用的「约束、放宽」思想，将询问操作进行一些约束，比如说，约束只能询问一些题目答案是否是正确。

那么观察新的询问，我们发现它等价于一个数学模型：

有一个未知的长度为 $n$ 的 $01$ 向量 $X$，你需要构造一个大小为 $q\times n$ 的 $01$ 矩阵 $A$，使得能够从返回的 $C=AX$ 唯一确定 $X$ 的值。

定义一个 $q\times n$ 的 $01$ 矩阵 $A$ 是合法的，当且仅当对于任意长度为 $q$ 的向量 $C$，$AX=C~(\forall i,X_i\in\{0,1\})$ 都有唯一解。那么我们的问题等价于构造一个合法的 $A$。

考虑增量构造 $A$。

$A=\begin{pmatrix}1\end{pmatrix}$ 是一个合法矩阵。

假设大小为 $q\times n$ 的矩阵 $A$ 是一个合法矩阵，那么可以如下构造一个大小为 $(2q)\times (2n+q)$ 的合法矩阵：

怎么通过这个矩阵还原 $x_1\sim x_{2n+q}$ 呢？首先根据 $c_i+c_{i+q}$ 的奇偶性得到 $x_{2n+1}\sim x_{2n+q}$。将 $A'$ 上下两部分相加就可以得到 $2$ 倍的子问题，递归可以计算出 $x_{1}\sim x_n$。将 $A'$ 下上两部分相减可以得到另一个 $2$ 倍的子问题，递归可以计算出 $x_{n+1}\sim x_{2n}$。

然后你就感觉到不太对，我们询问的 $A$ 应当是 $01$ 矩阵，但是我们构造出的矩阵存在 $-1$。

事实上，对于 $-1$ 的查询，我们可以将 $A$ 分裂为 $A_1-A_2$ 两次询问得到。

那么我们构造出的询问矩阵大小：$1\times1,2\times2,4\times8,\cdots,(2^i)\times((i+2)2^{i-1})$。询问次数为 $\mathcal{O}\left(\dfrac{n}{\log n}\right)$。

我们发现，因为 $-1$ 的存在，我们每次询问实际上需要问 $2$ 次，这是非常不优的。

考虑另一种构造，假设大小为 $q\times n$ 的矩阵 $B$ 是一个合法 $01$ 矩阵，大小为 $q\times n'$ 的矩阵 $A$ 是一个合法矩阵，设大小为 $q\times n'$ 的 $01$ 矩阵 $A_1,A_2$ 满足 $A_1-A_2=A$。那么可以如下构造一个大小为 $(2q)\times (n+n')$ 的合法矩阵：

怎么通过这个矩阵还原 $x_1\sim x_{n+n'}$ 呢？首先可以通过 $B'$ 的上下两部分相减得到 $A$ 的子问题，用上面的方法递归解决 $x_{n'+1}\sim x_{n+n'}$。剔除 $x_{n'+1}\sim x_{n+n'}$ 的影响后可以得到 $B$ 的子问题，可以递归解决。

那么我们构造出的询问矩阵大小：$1\times1,2\times2,4\times5,\cdots,(2^i)\times(i2^{i-1}+1)$。询问次数为 $\mathcal{O}\left(\dfrac{n}{\log n}\right)$，但是少了一半的常数。

思考这道题，发现我们如果直接用上面的方法构造，空间能够直接给你卡爆，迭代 $14$ 次后的矩阵有 $402530304$ 个位置有值。

所以考虑分块，经过实测，最多只能跑出来 $1024\times 5121$ 的矩阵。所以每 $5121$ 个数分一块解决就好了。询问次数为 $2^k\left\lceil\dfrac{n}{k2^{k-1}+1}\right\rceil~(k=10)$，最大为 $26624$。

::::success[参考代码]

#include<bits/stdc++.h>
using namespace std;
extern "C" {
extern int ask(int m, vector<int> w, vector<bool> ans);

const int B = 5121;
vector<vector<int>> W1[20];
vector<vector<bool>> W2[20];
void build1(int x) {
    static vector<vector<int>> A, AA;
    A = W1[x - 1];
    AA.clear();
    /*
    AA=(A -A I)
       (A  A 0)
    */
    for (int i = 0; i < A.size(); i++) {
        AA.push_back({});
        for (int x : A[i]) AA.back().push_back(x);
        for (int x : A[i]) AA.back().push_back(-x);
        for (int j = 0; j < A.size(); j++) AA.back().push_back(i == j);
    }
    for (int i = 0; i < A.size(); i++) {
        AA.push_back({});
        for (int x : A[i]) AA.back().push_back(x);
        for (int x : A[i]) AA.back().push_back(x);
        for (int j = 0; j < A.size(); j++) AA.back().push_back(0);
    }
    W1[x] = AA;
}
void build2(int x) {
    static vector<vector<int>> A, A1, A2;
    static vector<vector<bool>> B, BB;
    A = W1[x - 1];
    B = W2[x - 1];
    BB.clear();
    A1 = A2 = A;
    for (auto &x : A1) for (auto &y : x) y = y == 1;
    for (auto &x : A2) for (auto &y : x) y = y == -1;
    /*
    BB=(B A1)
       (B A2)
    */
    for (int i = 0; i < B.size(); i++) {
        BB.push_back({});
        for (auto x : B[i]) BB.back().push_back(x);
        for (auto x : A1[i]) BB.back().push_back(x);
    }
    for (int i = 0; i < B.size(); i++) {
        BB.push_back({});
        for (auto x : B[i]) BB.back().push_back(x);
        for (auto x : A2[i]) BB.back().push_back(x);
    }
    W2[x] = BB;
}
vector<bool> solve1(int x, vector<int> C) {
    if (x == 0) return {(bool)C[0]};
    vector<bool> X, X1, X2, X3;
    vector<int> C1, C2;
    int q = C.size() / 2;
    for (int i = 0; i < q; i++) X3.push_back((C[i] + C[i + q]) % 2);
    for (int i = 0; i < q; i++) C1.push_back((C[i] + C[i + q] - X3[i]) / 2);
    X1 = solve1(x - 1, C1);
    for (int i = 0; i < q; i++) C2.push_back((C[i + q] - C[i] + X3[i]) / 2);
    X2 = solve1(x - 1, C2);

    for (int v : X1) X.push_back(v);
    for (int v : X2) X.push_back(v);
    for (int v : X3) X.push_back(v);
    return X;
}
vector<bool> solve2(int x, vector<int> C) {
    if (x == 0) return {(bool)C[0]};
    vector<bool> X, X1, X2;
    vector<int> C1, C2;
    int n = W2[x - 1].back().size(), q = C.size() / 2;
    for (int i = 0; i < q; i++) C2.push_back(C[i] - C[i + q]);
    X2 = solve1(x - 1, C2);
    for (int i = 0; i < q; i++) {
        C1.push_back(C[i]);
        for (int j = n; j < W2[x][i].size(); j++) C1.back() -= W2[x][i][j] * X2[j - n];
    }
    X1 = solve2(x - 1, C1);

    for (auto x : X1) X.push_back(x);
    for (auto x : X2) X.push_back(x);
    return X;
}
vector<bool> solve(int n, int l) {
    for (int i = 1; ; i++) if (i * (1 << (i - 1)) + 1 >= n) {
        auto A = W2[i];
        vector<int> C;
        for (int j = 0; j < A.size(); j++) {
            A[j].resize(n);
            vector<int> qry;
            vector<bool> all;
            for (int k = 0; k < A[j].size(); k++) if (A[j][k]) qry.push_back(k + l), all.push_back(1);
            C.push_back(ask(qry.size(), qry, all));
        }
        auto X = solve2(i, C);
        X.resize(n);
        return X;
    }
}
vector<bool> work(int n) {
    W1[0] = {{1}}, W2[0] = {{1}};
    for (int i = 1; i <= 10; i++) build1(i), build2(i);
    vector<bool> X;
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(l + B - 1, n);
        auto res = solve(r - l + 1, l);
        for (auto v : res) X.push_back(v);
    }
    return X;
}
}

::::