题解：P7848 「JZOI-2」填问卷
ZnPdCo
·
·
题解
使用构造题常用的「约束、放宽」思想，将询问操作进行一些约束，比如说，约束只能询问一些题目答案是否是正确。
那么观察新的询问，我们发现它等价于一个数学模型：
有一个未知的长度为 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。
假设大小为 $q\times n$ 的矩阵 $A$ 是一个合法矩阵，那么可以如下构造一个大小为 $(2q)\times (2n+q)$ 的合法矩阵：
$$
A'=\begin{pmatrix}
A&-A&I\\
A&A&0
\end{pmatrix}
$$
怎么通过这个矩阵还原 $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')$ 的合法矩阵：
$$
B'=\begin{pmatrix}
B&A_1\\
B&A_2
\end{pmatrix}
$$
怎么通过这个矩阵还原 $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[参考代码]
```cpp
#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;
}
}
```
::::