研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。
作为研究的一部分，安德鲁采集了 $n$ 个蘑菇，编号为 $0$ 到 $n - 1$。每个蘑菇均为两种蘑菇种类之一，称为 $A$ 或 $B$。
安德鲁知道蘑菇 $0$ 属于种类 $A$，但是由于这两种蘑菇看起来很相似，他不知道蘑菇 $1$ 到 $n - 1$ 属于哪一种。
幸运的是，安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时，需要将两个或者多个蘑菇放到机器里，并摆成一排 (以任意顺序)，然后打开机器。接下来，这台机器会计算所有不属于同一种类的相邻蘑菇对的个数。例如，如果你把种类为 $\left[ A, B, B, A \right]$ 的蘑菇 (按照这个顺序) 放到机器中，结果应该是 $2$。
但是，因为机器操作非常昂贵，机器只能使用有限的次数。此外，在机器的所有使用中，放置到机器中的蘑菇总数不能超过 $10^5$。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 $A$ 的蘑菇。
你需要实现以下函数：
int count_mushrooms(int n)
以上函数可以调用以下函数：
int use_machine(std::vector <int> x)
use_machine 的所有调用中，所有被传到该函数 use_machine 的 $x$ 的总长度不能超过 $10^5$。首先可以明确的是：我们不可能在 $226$ 次内得到 $20000$ 个蘑菇种类的精确分布。
这是因为，要得到所有蘑菇的种类，所需要的信息量至少是 $19999 \,\mathrm{bits}$ (即不同情形总数为 $2^{19999}$)，而每次询问，即使 $n$ 开到最大 ($20000$) 也只能获得 $\log_2 n < 14.3 \,\mathrm{bits}$ 信息，因此所有信息能获得的总信息量小于 $14.3 \times 226 = 3231.8 \,\mathrm{bits} \ll 19999 \,\mathrm{bits}$。
因此我们需要利用题目返回值的性质 —— $A$ 类蘑菇的总数，即求某一类蘑菇的数量，而并不需要知道它们的精确分布。
(ps: 以下为了方便 (并融合代码)，我们将所有蘑菇看成一个 $\texttt 0/\texttt 1$ 串 $a$，$\texttt 0$ 表示 $A$ 类蘑菇，$\texttt 1$ 表示 $B$ 类蘑菇，那么题目所要求的返回值就是整个串中 $\texttt 0$ 的数量)
而题目提供的询问是，给定一个子序列 (但是并不一定要按照原序) $a_{n_1}, a_{n_2}, \cdots, a_{n_k}$，交互库会返回 $$ \sum_{i=1}^{k-1} \left[ a_{n_i} \neq a_{n_{i + 1}} \right] $$ 的值。
那如何利用这个信息去得到 $\displaystyle \sum_{i=1}^n a_i$ (虽然是这里统计的是 $B$ 类总数，但实质上是一样的) 的值呢？或者说，对于一个子序列 $a_{n_1}, a_{n_2}, \cdots, a_{n_k}$，去得到 $\displaystyle \sum_{i=1}^k a_{n_i}$ 的值呢？
一种简单的思路是：对于所有偶数位置 $m_{2 i}$，令其等于 $m_{2 i}$，而对所有奇数位置 $m_{2 i + 1}$，令它的值 $a_{m_{2 i + 1}}$ 恒为 $0$。那么 $$ \sum_{i=1}^{2 k} \left[ a_{m_i} \neq a_{m_{i + 1}} \right] = \sum_{i=1}^k \left( \left[ a_{m_{2 i - 1}} \neq a_{m_{2 i}} \right] + \left[ a_{m_{2 i}} \neq a_{m_{2 i + 1}} \right] \right) = 2 \sum_{i=1}^k a_{m_{2 i}} = 2 \sum_{i=1}^k a_{n_i} $$
这种方案看起来很棒棒，好像一步就可以了诶！但是注意题目的条件：$x$ 中的元素互不相同，而你一开始所能确定的，就只有 $a_1 = 0$ 啊！(嘿嘿出题人可没有那么傻让你白拿 100 分的)
那么这样我们就有一种策略了：
将整个过程分为前期和后期，前期想尽一切办法获得尽可能多的位置的精确值，设获得了 $A$ 个，然后由抽屉原理知 $0$ 或 $1$ 至少有 $\left \lceil \dfrac A2 \right \rceil$ 个。
于是在后期，通过这至少 $\left \lceil \dfrac A2 \right \rceil$ 个 $0$ (或 $1$)，每轮可以知道至少 $\left \lceil \dfrac A2 \right \rceil$ 个元素的和，于是通过 $O \left( \dfrac n A \right)$ 次询问获得最终答案。
首先，前期的询问次数有一个明显的上界 $O \left( A \right)$ (因为询问一次至少能获得一个位置的精确值)，因此总询问次数为 $O \left( A \right) + O \left( \dfrac n A \right) = O \left( \sqrt n \right)$ (当 $A = O \left( \sqrt n \right)$ 时)
喏，出现 $\sqrt n$ 了呢！和题目中的 $226$ 还是非常像的呵！(虽然说 $226$ 直观上更像 $\dfrac {\sqrt n} 2$)
不过，阶对了并不代表复杂度对了。如果按照这种最土的策略，那么可以将大 $O$ 前面的常数分析出来然后得上界为 $A + \dfrac {2 n} A + O \left( 1 \right) \geq \sqrt {2 n} + O \left( 1 \right)$ 是很劣的。
于是我们需要对前期和后期都需要做优化。
首先考虑后期。
我们按照 $\left[ 0, n_1, 0, n_2, 0, \cdots, 0, n_k, 0 \right]$ 的策略虽然可以获得结果，但是可以注意到我们获得的结果一定是一个偶数，而这会使人感觉比较浪费。
事实上，我们可以在序列末尾添加一个 $x$，使之变成 $\left[ 0, n_1, 0, n_2, 0, \cdots, 0, n_k, 0 \color {fuchsia} {, x} \right]$，这样记原来的答案 ($\displaystyle \sum_{i=1}^k a_{n_i}$) 为 $ans$，那么返回值就等于 $2 ans + a_x$。注意到 $a_x \in \left\{ 0, 1 \right\}$，因此我们不但能获得 $ans$ 还能获得 $a_x$，一举两得呢！
更进一步的是，我们获得的 $a_x$ 其实是 $x$ 位置的精确值，也就是说，我们在后期的每个操作，还能够使 $A$ 值每一步加 $1$ 呢！
因此，设后期开始时的 $A$ 值为 $A_0$，那么后期的询问次数上界将不再是 $\dfrac {2 n} {A_0} + O \left( 1 \right)$ 而是 $$ \frac {4 n} {A_0 + \sqrt {A_0^2 + 4 n}} + O \left( 1 \right) = \frac {2 n} {A_0 \left( 1 + n \middle / A_0^2 \right)} + O \left( \dfrac {n^3} {A_0^5} \right) $$
接下来考虑前期。
首先，前期主要是打 "小策略战" —— 即利用较小的次数获得较多的即时信息。
当我们获得即时信息越来越多，我们能利用的 $0$ 和 $1$ 也越来越多，也就越来越强，又颇有一番养成类游戏的风味。
前期除了询问 $\left[ 0, i \right]$ 获得 $a_i$ 外，最经典的一个策略莫过于询问 $\left[ 0, i, 0, j \right]$ 获得 $2 a_i + a_j$，然后利用 $a_i, a_j \in \left\{ 0, 1 \right\}$ 来同时取得 $a_i, a_j$ 了。
(于是你就喜提 $244$ 步，$92.62$ 分)
那怎么获得更好的策略呢？我们可以参考后期，每次的询问都是 $\left[ 0, n_1, 0, n_2, 0, \cdots, 0, n_k, 0, x \right]$ 的格式，这样可以奇偶性可以立即获得 $x$，然后对于其它的信息只能获得它的和。
下面定义一些即时策略的参数：容量 $C$，一个策略所需要用到的 $0$ 的数量的峰值减 $1$，即上式中 $k$ 的最大值；净利润 $P$，除 $x$ 外可以获得精确值的数量；时间 $t$，表示这个策略所需要进行的询问次数；利润 $P_\mathrm k$，它等于 $P + t$，表示这一轮可以获得总的精确值的数量；净效率 $\eta$，它被定义为 $\dfrac Pt$；效率 $\eta_\mathrm k$，它被定义为 $\dfrac {P_\mathrm k} t$，也等于 $\eta + 1$，效率衡量的是一个策略在单位时间内获得的位置数量。
$P_\mathrm k = P + t$ 很好理解，因为每一轮的 $x$ 都是能立即获得的，因此 $t$ 轮询问就可以获得 $t$ 个额外值，又除了诸 $x$ 外一共能获得 $P$ 个值，因此总共可以获得 $P + t$ 个值。
就以上面最基础的 $\left[ 0, i, 0, j \right]$ 策略为例，它满足：$\color {fuchsia} {C = 1, P = 1, t = 1, P_\mathrm k = 2, \eta = 1, \eta_\mathrm k = 2}$。当然我们还可以定义策略表 $T$ 表示对于要获得的 $P$ 个值，$t$ 轮询问每一轮应该询问哪些数。如上面的例子中策略表就是 $\left[ \left\{ 1 \right\} \right]$。
上面的策略太浅显了，下面我们再来举一个具体的例子，来观察以下如何定量刻画一个策略。
这个策略我们利用 $t = 3$ 轮时间获得 $P_\mathrm k = 7$ 个位置的值，从而它的效率 $\eta_\mathrm k = \dfrac 73$ 比上面的策略 ($2$) 高。
由于 $P = P_\mathrm k - t = 4$，因此我们记四个元素为 $a, b, c, d$，则我们的策略表为 $\left[ \left\{ a, b \right\}, \left\{ a, c \right\}, \left\{ b, c, d \right\} \right]$。
(ps: 当然如果我们将元素记为 $1, 2, 3, 4$ 的话 $T = \left[ \left\{ 1, 2 \right\}, \left\{ 1, 3 \right\}, \left\{ 2, 3, 4 \right\} \right]$。下面的策略总表就用这种格式)
为什么上面的策略可行呢？这是因为，当我们获得 $a + b, a + c, b + c + d$ 时，将其相加，可以获得 $2 \left( a + b + c \right) + d$，从而由 $d \in \left\{ 0, 1 \right\}$ 可以同时获得 $a + b + c$ 和 $d$。结合 $a + b, a + c$ 就能同时得到 $a, b, c$。
这时人工证明一个策略合法的过程。但是人工证明一个策略肯定很繁琐，而且对于不同的策略还要写一大堆 if/else，肯定很烦。
那怎么办呢？考虑用机器证明啊！其实也不叫证明，就是一个验证。事实上，当 $P$ 不大时，我们可以直接验证所有变量取 $0$ 或 $1$ 的 $2^P$ 种组合，检验将它们代入到策略表后的 $t$ 元组是否互不相同即可。
如果是，那么这个策略合法。而且通过策略还原变量也只要枚举，而这一切只需要将我们的 $P$ 控制地不太大即可。
那下面我们就给出我们的策略总表了。这些策略有些是构造出来的，有些是搜出来的。
| 编号 | 名称 | 时间 $t$ | 容量 $C$ | 净利润 $P$ | 利润 $P_\mathrm k$ | 净效率 $\eta$ | 效率 $\eta_\mathrm k$ | 策略表 $T$ |
|---|---|---|---|---|---|---|---|---|
| 1 | simple | $1$ | $1$ | $1$ | $2$ | $1$ | $2$ | $\left[ \left\{ 1 \right\} \right]$ |
| 2 | double simple | $2$ | $1$ | $2$ | $4$ | $1$ | $2$ | $\left[ \left\{ 1 \right\}, \left\{ 2 \right\} \right]$ |
| 3 | alternating triple | $3$ | $3$ | $4$ | $7$ | $\dfrac 43 \approx 1.33$ | $\dfrac 73 \approx 2.33$ | $\left[ \left\{ 1, 2 \right\}, \left\{ 1, 3 \right\}, \left\{ 2, 3, 4 \right\} \right]$ |
| 4 | three plus one | $4$ | $3$ | $5$ | $9$ | $\dfrac 54 = 1.25$ | $\dfrac 94 = 2.25$ | $\left[ \left\{ 1, 2 \right\}, \left\{ 1, 3 \right\}, \left\{ 1, 4 \right\}, \left\{ 2, 3, 5 \right\} \right]$ |
| 5 | three slot ultimate | $5$ | $3$ | $7$ | $12$ | $\dfrac 75 = 1.40$ | $\dfrac {12} 5 = 2.40$ | $\left[ \left\{ 1, 2 \right\}, \left\{ 1, 3, 4 \right\}, \left\{ 2, 3, 5 \right\}, \left\{ 2, 4, 6 \right\}, \left\{ 4, 5, 7 \right\} \right]$ |
| 6 | six augmented | $6$ | $4$ | $9$ | $15$ | $\dfrac 32 = 1.50$ | $\dfrac 52 = 2.50$ | $\left[ \left\{ 1, 2, 3 \right\}, \left\{ 1, 4, 5 \right\}, \left\{ 2, 6, 7 \right\}, \left\{ 3, 4, 6, 8 \right\}, \left\{ 2, 3, 4, 9 \right\}, \left\{ 1, 3, 6, 9 \right\} \right]$ |
| 7 | eight power final | $8$ | $5$ | $13$ | $21$ | $\dfrac {13} 8 \approx 1.63$ | $\dfrac {21} 8 \approx 2.63$ | \begin{array}c \left[ \left\{ 1, 2, 3, 4, 5 \right\}, \left\{ 1, 4, 7, 8, 10 \right\}, \left\{ 1, 3, 7, 9, 10 \right\}, \left\{ 1, 2, 8, 9, 10 \right\}, \\ \left\{ 6, 7, 8, 9, 10 \right\}, \left\{ 1, 2, 6, 7, 11 \right\}, \left\{ 1, 3, 6, 8, 12 \right\}, \left\{ 1, 4, 6, 9, 13 \right\} \right] \end{array} |
(Bonus: 可以证明，当 $t, C \to \infty$ 时，策略的效率 $\eta_\mathrm k$ 可以任意大，即对于 $\forall N$ 总存在某个策略的效率大于 $N$。当然这个结论可能只有理论作用了呵呵)
可以发现这些策略从上往下效率是基本递增的 (也就是说下面的效率会比上面的高效)
不过，高效的策略的两个普遍代价就是：时间较长、容量较大。因此我们一开始只能使用前面的 "低效策略"，当我们获得的 $0$ 和 $1$ 越来越多，我们就可以大胆使用 "高效策略" 了。
事实上，策略 6 (six augmented) 和策略 7 (eight power final) 的最终效率 $\eta_\mathrm k$ 都达到了 $2.5$，足以在 $226$ 次询问内完成本题了。
在前后期均加满优化后，$226$ 次询问就是绰绰有余的，在最坏情况下的分析可以见下表：
| 编号 | 当前总询问次数 $q$ | 已知精确值个数 $C_0$ | 可用容量 $\left \lceil \dfrac {C_0} 2 \right \rceil - 1$ | 已知总和值个数 $S$ | 下一步使用策略 | |
|---|---|---|---|---|---|---|
| 1 | $0$ | $1$ | $0$ | $1$ | 直接询问 | |
| 2 | $1$ | $2$ | $0$ | $2$ | 直接询问 | |
| 3 | $2$ | $3$ | $1$ | $3$ | 策略 2 (double simple) | |
| 4 | $4$ | $7$ | $3$ | $7$ | 策略 5 (three slot ultimate) | |
| 5 | $9$ | $19$ | $9$ | $19$ | 策略 8 (eight power final) | |
| 6 | $17$ | $40$ | $19$ | $40$ | 策略 8 (eight power final) | |
| 7 | $25$ | $61$ | $30$ | $61$ | 策略 8 (eight power final) | |
| 8 | $33$ | $82$ | $40$ | $82$ | 策略 8 (eight power final) | |
| 9 | $41$ | $103$ | $51$ | $103$ | 策略 8 (eight power final) | |
| 10 | $49$ | $124$ | $61$ | $124$ | 策略 8 (eight power final) | |
| 11 | $57$ | $145$ | $72$ | $145$ | 策略 8 (eight power final) | |
| 12 | $65$ | $166$ | $82$ | $166$ | 策略 8 (eight power final) | |
| 13 | $73$ | $187$ | $93$ | $187$ | 策略 8 (eight power final) | |
| 14 | $81$ | $208$ | $103$ | $208$ | 策略 8 (eight power final) | |
| 15 | $89$ | $229$ | $114$ | $229$ | 进入后期 | |
| 16 | $90$ | $230$ | $114$ | $344$ | / | |
| 17 | $91$ | $231$ | $115$ | $459$ | / | |
| 18 | $92$ | $232$ | $115$ | $575$ | / | |
| 19 | $93$ | $233$ | $116$ | $691$ | / | |
| 20 | $94$ | $234$ | $116$ | $808$ | / | |
| 21 | $95$ | $235$ | $117$ | $925$ | / | |
| 22 | $96$ | $236$ | $117$ | $1043$ | / | |
| 23 | $97$ | $237$ | $118$ | $1161$ | / | |
| 24 | $98$ | $238$ | $118$ | $1280$ | / | |
| 25 | $99$ | $239$ | $119$ | $1399$ | / | |
| 26 | $100$ | $240$ | $119$ | $1519$ | / | |
| $\cdots$ | ||||||
| 142 | $216$ | $356$ | $178$ | $18803$ | / | |
| 143 | $217$ | $357$ | $179$ | $18981$ | / | |
| 144 | $218$ | $358$ | $179$ | $19160$ | / | |
| 145 | $219$ | $359$ | $180$ | $19339$ | / | |
| 146 | $220$ | $360$ | $180$ | $19519$ | / | |
| 147 | $221$ | $361$ | $181$ | $19699$ | / | |
| 148 | $222$ | $362$ | $181$ | $19880$ | / | |
| 149 | $223$ | $363$ | $182$ | $\color {fuchsia} {20000}$ | 结束 | |
#include "mushrooms.h"
#include <bits/stdc++.h>
#define EB emplace_back
#define popc __builtin_popcount
#define ctz __builtin_ctz
#define OK (*Z + Z[1])
namespace mushrooms {
typedef std::vector <int> vector;
const int N = 40054;
int n, n_query, Z[2];
int a[N], seq[N];
vector pool[2];
inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline int min(const int x, const int y) {return x < y ? x : y;}
inline int max(const int x, const int y) {return x < y ? y : x;}
inline void trace() {fprintf(stderr, "[time %3d] %d : %d, progress: {A : %d, B : %d, tot : %d/%d}\n", n_query, (int)pool->size(), (int)pool[1].size(), *Z, Z[1], OK, n);}
inline void set(int h, int v) {a[h] = v, pool[v].EB(h), ++Z[v];}
inline int query(const vector &seq) {return ++n_query, use_machine(seq);}
namespace first_four {
void main() {
switch (query({0, 1, 2, 3})) {
case 0: set(1, 0), set(2, 0), set(3, 0); break;
case 1:
set(3, 1);
switch (query({0, 2, 1})) {
case 0: set(1, 0), set(2, 0); break;
case 1: set(1, 1), set(2, 1); break;
case 2: set(1, 0), set(2, 1); break;
}
break;
case 2:
set(3, 0);
switch (query({0, 1, 3, 2})) {
case 1: set(1, 0), set(2, 1); break;
case 2: set(1, 1), set(2, 0); break;
case 3: set(1, 1), set(2, 1); break;
}
break;
case 3: set(1, 1), set(2, 0), set(3, 1); break;
}
assert(*Z + Z[1] == 4);
}
}
namespace expanding {
const int expand_table[8][11] = {
{},
// times, slots, new, strategy
{1, 1, 1, 1},
{2, 1, 2, 1,2},
{3, 3, 4, 3,5,14},
{4, 3, 5, 3,5,9,22},
{5, 3, 7, 3,13,22,42,88},
{6, 4, 9, 7,25,98,172,270,293},
{8, 5, 13, 31,713,837,899,992,1123,2213,4393},
};
int tmp[10], col[25];
void expand(const int *e, bool rev) {
int i, S, y, z = 0, t = e[0], slot = e[1], len = e[2], main_L = OK, aux_L = main_L + len;
for (i = 1; i <= 2 * slot + 1; i += 2) seq[i] = pool[rev][z++];
for (i = 0; i < t; ++i) {
*seq = aux_L + i, y = 0;
for (S = e[3 + i]; S; S &= S - 1) seq[2 * ++y] = main_L + ctz(S);
S = query(vector(seq, seq + 2 * (y + 1))),
col[len + i] = (S ^ rev) & 1, S >>= 1, tmp[i] = rev ? y - S : S;
}
for (S = 0; S < 1 << len; ++S) {
for (i = 0; i < t && popc(S & e[3 + i]) == tmp[i]; ++i);
if (i == t) break;
}
assert(S != 1 << len);
for (i = 0; i < len; ++i) col[i] = S >> i & 1;
for (i = 0; i < len + t; ++i) set(main_L + i, col[i]);
}
void main() {
int i, w = max(pool[0].size(), pool[1].size()), rem = n - OK; const int *e;
if (assert(--w > 0), rem == 1) return set(OK, query({0, OK}));
for (i = 7; i > 0; --i) {
e = expand_table[i];
if (e[1] <= w && e[0] + e[2] <= rem)
return expand(e, pool[0].size() < pool[1].size());
}
throw "gg";
}
}
namespace sweeping {
void sweep(int w, bool rev) {
int i, S, main_L = OK;
for (i = 0; i < w; ++i) seq[2 * i] = main_L + i, seq[2 * i + 1] = pool[rev][i];
S = query(vector(seq, seq + 2 * w)),
set(main_L, (S ^ rev) & 1), S >>= 1, Z[!rev] += S, Z[rev] += w - 1 - S;
}
inline void main() {sweep(min(max(pool[0].size(), pool[1].size()), n - OK), pool[0].size() < pool[1].size());}
}
int count_mushrooms(int n_) {
int i;
n = n_, n_query = 0, pool->EB(0), *Z = 1, Z[1] = 0;
memset(a, -1, n << 2), trace();
if (n < 4) for (i = 1; i < n; ++i) set(i, query({0, i})), trace();
else {
for (first_four::main(); trace(), OK < n; expanding::main())
if (pool[0].size() >= 120 || pool[1].size() >= 120) break;
for (; OK < n; ) sweeping::main(), trace();
}
return assert(OK == n), *Z;
}
}
int count_mushrooms(int n) {return mushrooms::count_mushrooms(n);}
坑1：事实上可以通过效率稍大的策略 (如 $t = 16, P_\mathrm k = 49$ 的策略) 从而可以在更少的次数内完成问题。但这个范围的 $P$ ($33$) 就不能通过单纯的枚举了，需要通过人工方法进行还原，从而造成代码量的提升。
坑2：在进行类似 $\left[ 0, n_1, 0, n_2, \cdots \right]$ 的操作的时候有时候是 $1$ 比 $0$ 多，此时需要将所有 (用来固定的) $0$ 改成 $1$，最后不要忘记取反。
坑3：在 loj 上可能因为奇奇怪怪的原因造成命名冲突，可以通过创造匿名 namespace 的方法来解决。