本题是一道送分题提交答案题。

题目背景

在 2042 年，一个计算机计算模型从理论走到了现实，实现大规模普及。

您是当年 ION 的考生，需要用这个模型实现 20 个任务……

这时您从梦中惊醒，发现自己在做国家集训队互测，需要用这个模型去实现 20 个任务……

题目描述

本题是一道提交答案题。

最简题意：给您一个checker.cpp，请生成可以通过的20个输出文件quantum1.out, quantum2.out, ..., quantum20.out。

请参考下方附录1了解该模型的计算原理。您需要在这个模型上完成 20 个任务，见下方任务要求。

输出格式

为了避免交互可能导致的用时过长、您的程序在运行时记录一些东西、随机的时候有概率因素影响结果等问题，本题采用提交答案。注意，本题区分大小写。

任务要求中具体指出每个点有几个代码块，每个代码块需要由 Begin 开始，End 结束，在代码块中，只有顺序结构和分支结构。

可用的比特从 0 开始编号。如果对单个比特进行操作，若无角度参数，可以使用 <op> <id> <controller ids>，其中 <op> 为 H T X Y Z中的一个，<id> 为操作比特的编号，<controller ids> 以二进制形式存储某个比特是否为控制比特。具体地，第 $i$ 个比特为控制比特当且仅当 <controller ids> 二进制下 $2^i$ 位为 1。注意，不允许编号超过范围，<controller ids>的最高位也不能超过范围，同时被操作的比特不允许是控制比特；若有角度参数，可以使用 <op> <id> <theta> <controller ids>，其中 <op> 为 Rx Ry Rz 中的一个，<theta> 为角度参数，以弧度为单位，其余参数同上。若要交换两个比特，可使用 SWAP <id1> <id2> <controller ids> 交换两个编号为 <id1> 和 <id2> 的比特，注意这两个比特不允许相同。

若要读取一个比特的值，可以使用 IfM <id> <statements> [Else <statements>] Endif 或 M <id>，<id> 为编号。其中 IfM 为分支结构，若读取到 1 则会执行 IfM 与与它匹配的 Else（若无 Else 则为 Endif）之间的语句，否则若有匹配的 Else 的话，会执行 Else 与 Endif 之间的语句。如果使用 M 则会记录此时的结果并继续执行。注意：IfM 语句块中不允许使用 M。

一个代码块可以有返回值，可以为 $-2^{31}$ 到 $2^{31}-1$ 之间的任意值，默认为 0。可使用 Return <ret>，则会立刻结束这个代码块，并且返回 ret。也可以使用 ReturnFull <ret0> <ret1> ... <ret2^k-1>，共 $2^k$ 个值，其中 $k$ 为这个代码块从 Begin 到目前为止的 M 的个数，若 M 得到的读取结果分别为 $x_0, x_1,\cdots, x_{k-1}$，则会返回第 $\sum_{i=0}^{k-1} 2^ix_i$（从0开始编号）个值。

提示：可在下发的 template.cpp 上更改，并使用 quantum::Printer 进行输出（可参考附录2）。需和 quantum.cpp 一起编译。如
g++ template.cpp quantum.cpp -o <生成的可执行文件> -std=c++11
直接运行可生成 20 个输出。若想生成特定数据点，可使用
./<生成的可执行文件> <case_no> [<output_file>]
得到第 <case_no> 个数据点的输出在 <output_file>（默认为quantum<case_no>.out）。

任务要求

以下语句个数指的是一个代码块中的，不包括Begin End Else Endif。以下非大小关系的概率误差不允许超过 $10^{-6}$；要求的状态与生成的可以相差一个 $e^{i\theta}$（常数倍），且可以有 $10^{-6}$ 的绝对误差（具体参考 checker.cpp 的实现，但一般实现不回超过）；若不为固定的输入，要求生成特定的输出，则要求相差的 $e^{i\theta}$ 对所有输入均为一个常数。

提示：不保证按照难度排序。 一切以 checker 为准。（若遇到题意与 checker 矛盾可在群里反馈。）

样例1

1 个代码块，1 个比特，初始状态为 $|0\rangle$。实现一个随机数生成器，以 $1/2$ 的概率返回 0，$1/2$ 的概率返回 1。
限制：这个代码块中语句个数不超过 3，不允许使用 IfM，至多使用 1 个 M。
参考答案为下发文件中 quantum_sample1.out。

任务1

1 个代码块，1 个比特，初始状态为 $|0\rangle$。实现一个随机数生成器，以 $14343375/16777216$ 的概率返回 14343375，$1-14343375/16777216$ 的概率返回 0。
限制：这个代码块中语句个数不超过 3，不允许使用 IfM，至多使用 1 个 M。

任务2

1 个代码块，1 个比特，初始状态为 $|0\rangle$。实现一个随机数生成器，以 $1/4$ 的概率返回 1，以 $1/4$ 的概率返回 2，以 $1/4$ 的概率返回 3，以 $1/4$ 的概率返回 4。
限制：这个代码块中语句个数不超过 5，不允许使用 Rx Ry Rz IfM，至多使用 2 个 M。

任务3

1 个代码块，1 个比特，初始状态为 $|0\rangle$。实现一个随机数生成器，以 $10\%$ 的概率返回 1，以 $20\%$ 的概率返回 2，以 $30\%$ 的概率返回 3，以 $40\%$ 的概率返回 4。
限制：这个代码块中语句个数不超过 20，不允许使用 M，至多使用 3 个 IfM。

任务4

1 个代码块，1 个比特，初始状态为 $|0\rangle$。实现一个随机数生成器，以 $10\%$ 的概率返回 1，以 $20\%$ 的概率返回 2，以 $30\%$ 的概率返回 3，以 $40\%$ 的概率返回 4。
限制：这个代码块中语句个数不超过 20，不允许使用 IfM，至多使用 3 个 M。

任务5

1 个代码块，1 个比特，初始状态为 $|0\rangle$。生成 $(\sqrt{0.1}+\sqrt{0.2}i)|0\rangle+(\sqrt{0.3}+\sqrt{0.4}i)|1\rangle$。
限制：这个代码块中语句个数不超过 5，不允许使用 IfM M。

任务6

1 个代码块，1 个比特，初始状态为 $(|0\rangle+i|1\rangle)/\sqrt2$ 或 $(|0\rangle-i|1\rangle)/\sqrt2$。若为 $(|0\rangle+i|1\rangle)/\sqrt2$ 则返回 1，否则返回 0. 限制：这个代码块中语句个数不超过 8，不允许使用 Rx Ry Rz，至多使用 1 个 M，至多使用 1 个 IfM。

任务7

伊利泽-威德曼炸弹测试问题。
2 个代码块，1 个比特。初始状态为 $|0\rangle$，会先执行第一个代码块，然后会有两种情况：

1. 有“炸弹”读取这个比特的值，如果为 1 则爆炸，不会继续执行；
2. 不会进行任何操作。 然后执行第二个代码块，得到返回值 1 或 -1，其中 1 表示一定有“炸弹”，-1 表示不确定。要求：若没有“炸弹”则返回值为 1 的概率不超过 $10^{-6}$；若有炸弹，则爆炸的概率要小于 $60\%$，且不爆炸且返回 1 的概率要大于 $20\%$。
   限制：第一个代码块中语句个数不超过 2，不允许使用 IfM M；第二个代码块中语句个数不超过 5，至多使用 1 个 M，至多使用 1 个 IfM。

任务8

1 个代码块，2 个比特，初始状态为 $|00\rangle$。生成 $(|00\rangle+i|10\rangle+i|01\rangle-|11\rangle)/2$。
限制：这个代码块中语句个数不超过 2，不允许使用 IfM M。

任务9

1 个代码块，2 个比特，交换这两个比特（即实现 SWAP）。
限制：这个代码块中语句个数不超过 5，不允许使用 SWAP M IfM。

任务10

1 个代码块，2 个比特，初始状态为 $|00\rangle$，生成 $(|10\rangle-|01\rangle)/\sqrt{2}$。
限制：这个代码块中语句个数不超过 5，不允许使用 IfM M Rx Ry Rz。

任务11

1 个代码块，2 个比特，初始状态为 $|00\rangle$。生成 $\sqrt{0.1}|00\rangle+\sqrt{0.2}|10\rangle+\sqrt{0.3}|01\rangle+\sqrt{0.4}|11\rangle$。
限制：这个代码块中语句个数不超过 5，不允许使用 IfM M Rx Ry Rz。

任务12

1 个代码块，7 个比特，初始状态为 $|0000000\rangle$。生成 $(|1000000\rangle+|0100000\rangle+|0010000\rangle+|0001000\rangle+|0000100\rangle+|0000010\rangle+|0000001\rangle)/\sqrt{7}$。
限制：这个代码块中语句个数不超过 15，不允许使用 IfM M。

任务13

1 个代码块，8 个比特，初始状态为 $|00000000\rangle$。生成 $(|10000000\rangle+|01000000\rangle+|00100000\rangle+|00010000\rangle+|00001000\rangle+|00000100\rangle+|00000010\rangle+|00000001\rangle)/\sqrt{8}$。
限制：这个代码块中语句个数不超过 20，不允许使用 IfM M Rx Ry Rz。

任务14

1 个代码块，5 个比特，初始状态为 $|00000\rangle$。生成 $(|11000\rangle+|10100\rangle+|10010\rangle+|10001\rangle+|01100\rangle+|01010\rangle+|01001\rangle+|00110\rangle+|00101\rangle+|00011\rangle)/\sqrt{10}$。（含有所有含两个1的。）
限制：这个代码块中语句个数不超过 30，不允许使用 IfM M。

任务15

1 个代码块，6 个比特，初始状态为 $|000000\rangle$。生成 $(|111000\rangle+|110100\rangle+\cdots+|000111\rangle)/\sqrt{20}$。（含有所有含 3 个 1 的。）
限制：这个代码块中语句个数不超过 35，不允许使用 IfM M。

任务16

1 个代码块，4 个比特，要求对一个系数，如果它的基向量的第0、1、2位有奇数个比特为1，则将第3位取反（0变1，1变0）。即把 $|x_0x_1x_2x_3\rangle$ 的系数变为 $|x_0x_1x_2(x_3\operatorname{xor} [x_0,x_1,x_2\texttt{中有奇数个}1])\rangle$ 的系数。
限制：这个代码块中语句个数不超过 5，不允许使用 IfM M。

任务17

1 个代码块，5 个比特，要求对一个系数，如果它的基向量的第0、1、2、3位恰有1个比特为1，则将第4位取反（0变1，1变0）。即把 $|x_0x_1x_2x_3x_4\rangle$ 的系数变为 $|x_0x_1x_2x_3(x_4\operatorname{xor} [x_0,x_1,x_2,x_3\texttt{中恰有一个}1])\rangle$ 的系数。
限制：这个代码块中语句个数不超过 10，不允许使用 IfM M。

任务18

2 个代码块，2 个比特。初始状态为 $(|00\rangle-|01\rangle)/\sqrt{2}$，会先执行第一个代码块，然后会有两种情况：

1. 执行 X 1 1，即以第0个比特为控制比特，进行
2. 不会进行任何操作。
   然后执行第二个代码块，得到返回值 1 或 0，其中 1 表示一定有执行 X 1 1，0 表示一定没有执行。
   限制：第一个代码块中语句个数不超过 2，不允许使用 IfM M；第二个代码块中语句个数不超过 5，至多使用 1 个 M，至多使用 1 个 IfM。两个代码块中均不能使用第1个比特。（无论是操作、读取还是作为控制比特。）

任务19

4 个代码块，3 个比特，初始状态为 $|000\rangle$。先执行第1个代码块，然后分别执行三个代码块，实现三个随机数生成器，三个代码块返回值为 0 或 1，且一共返回奇数个 1，且四种情况等概率。
限制：第1个代码块中语句个数不超过 4，其余代码块中语句个数不超过 2，均不允许使用 IfM；第1个代码块不允许使用 M，其余代码块至多使用 1 个 M。第2个代码块只能使用第0个比特，第3个代码块只能使用第1个比特，第4个代码块只能使用第2个比特。

任务20

5 个代码块，2 个比特，初始状态为 $|00\rangle$。先执行第1个代码块，然后第2、3个代码块中恰执行一个，返回一个 0 或 1，第4、5个代码块中恰执行一个， 返回一个 0 或 1。要求：当执行第2、4个代码块时，两个返回值相同且均为0与均为1概率相同；执行第3、5个代码块时，两个返回值在四种情况中概率相同。 限制：所有代码块中语句个数各不超过 5，均不允许使用 IfM；第1个代码块不允许使用 M，其余代码块至多使用 1 个 M。第2、3个代码块只能使用第0个比特，第4、5个代码块只能使用第1个比特。

如何测试你的输出

在终端中先切换到存放该试题的目录下（假设该目录下已经有 checker.cpp、 testlib.h 以及你的输出文件），使用
g++ checker.cpp -o checker -std=c++14
编译 checker.cpp，再使用
./checker <case_no> [<output_file>]
命令检测 output_file（默认为quantum<case_no>.out）能否通过第 <case_no> 个测试数据。如
./checker 7
将检测 quantum7.out 能否通过第 7 个测试数据。若检测样例则 <case_no> 为 -1，此时须指定输出文件。同时，该 checker 支持一般的使用 testlib.h 的交互方式，即 ./checker <input> <output> <answer> ，<output> 为您的输出文件，输入文件 <input> 中应有一个1~20的正整数，表示测试点编号（可直接使用下发文件中quantum<case_no>.in）， <answer> 对结果没有影响，最终评测与该评测方式等价。

此外，您还可以通过运行 ./checker 检测全部 20 个点。但这个检测没有使用 testlib 的输入检测，所以可能这里能过，但不能通过上面的测试。通常只要输出中整数不会造成读入时溢出、小数按正常写法（不按科学计数法、无 nan，inf）就不会造成误判。

附录1：非传统的计算机模型

（遇到难以理解的地方可以在群里提问或根据下方参考资料自行搜索。）

在这个模型当中，若它有 $n$ 个比特，则（可以看作）它的内部有 $2^n$ 个复数参数 $w_0, w_1, \cdots w_{2^n-1}$，可以表示这个模型的一个状态。为了方便，可以把这 $2^n$ 个参数写成一个列向量，而这个列向量的第 $i$ 个（标准）基向量通常记作 $|x_0\cdots x_{n-1}\rangle$，其中 $i=\sum_{k=0}^{n-1}2^kx_k$。

对单个比特的操作：一种操作对应一种酉矩阵$U$（它的共轭转置是它的逆），其中 $$H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix},T=\begin{bmatrix}1&0\\0&e^{i\pi/4}\end{bmatrix},X=\begin{bmatrix}0&1\\1&0\end{bmatrix},Y=\begin{bmatrix}0&-i\\ i&0\end{bmatrix},Z=\begin{bmatrix}1&0\\0&-1\end{bmatrix},$$ $$Rx(\theta)=\begin{bmatrix}\cos(\theta/2)&-i\sin(\theta/2)\\-i\sin(\theta/2)&\cos(\theta/2)\end{bmatrix},Ry(\theta)=\begin{bmatrix}\cos(\theta/2)&-\sin(\theta/2)\\\sin(\theta/2)&\cos(\theta/2)\end{bmatrix},Rz(\theta)=\begin{bmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{bmatrix}.$$

当它作用于第 $i$ 个比特时，状态会发生变化 $w\to w'$，具体地， $$\begin{bmatrix}w'_{|x_0\cdots x_{i-1}0 x_{i+1}\cdots x_{n-1}\rangle}\\ w'_{|x_0\cdots x_{i-1}1 x_{i+1}\cdots x_{n-1}\rangle}\end{bmatrix}=U\begin{bmatrix}w_{|x_0\cdots x_{i-1}0 x_{i+1}\cdots x_{n-1}\rangle}\\ w_{|x_0\cdots x_{i-1}1 x_{i+1}\cdots x_{n-1}\rangle}\end{bmatrix}$$

如 $X|0\rangle=|1\rangle,X|1\rangle=|0\rangle,H|0\rangle=(|0\rangle+|1\rangle)/\sqrt2,H|1\rangle=(|0\rangle-|1\rangle)/\sqrt2,H((|0\rangle+|1\rangle)/\sqrt2)=|0\rangle,H((|0\rangle-|1\rangle)/\sqrt2)=|1\rangle$。如果有多个比特，则相当于对其他比特相同、将第 $i$ 个比特为0与1的两个系数进行变换。

对于交换，可看成 $$SWAP_{ij}=\begin{bmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\\0&0&0&1\end{bmatrix}$$

关于控制比特：当有控制比特时，我们会只对控制比特全为1的那些基向量所对应的系数进行操作。其中被操作的比特不能是控制比特。例如当一共 2 个比特时，直接对0比特操作 X 可以看作 $$\begin{bmatrix}0&1&0&0\\1&0&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$ 若第1个比特是控制比特，则矩阵可以看作 $$\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$

关于读取比特。读取第 $i$ 个比特时，结果为 0 的概率为状态中第 $i$ 个比特为 0 的所有系数的模长的平方和，结果为 1 的概率为状态中第 $i$ 个比特为 1 的所有系数的模长的平方和。可以证明在所有非读取操作前后，所有系数模长的平方和保持不变，始终为 $1$。（初始为 $|0\cdots0\rangle$。）若读取结果为 0，则会把对应第 $i$ 个比特为1的所有系数设为0，且其余系数同时乘以一个常数，使得所有系数的模长的平方和仍为1。读取结果为 1 同理。

例如：初始为 $|00\rangle$，对第0个比特进行 H后得到 $(|00\rangle+|10\rangle)/\sqrt{2}$，再以第0个比特为控制比特，对第1个比特进行 X 可以得到 $(|00\rangle+|11\rangle)/\sqrt{2}$，之后读取第一个比特，有 $1/2$ 的概率得到 0，且此时为 $|00\rangle$；有 $1/2$ 的概率得到 1，且此时为 $|11\rangle$；则此时再读取第1个比特，得到的结果必和前一次读取结果一样。

附录2：下发文件说明

注：若需更改，更改前建议备份。

checker.cpp 为检验器。与最终测试的 checker 相同。

template.cpp 为方便您得到输出文件的模板。只需要使用 ot 的输出功能即可，不需要自己开文件。

examples.cpp 为一个例子和一个样例（以五五开的概率生成 01 的生成器）。需要和 quantum.cpp 一起编译。如
g++ examples.cpp quantum.cpp -o examples -std=c++11

quantum.cpp 和 quantum.h 为库文件。里面包含模拟器 Simulator，执行器 Evaluator，以及打印输出文件的工具 Printer，均为命名空间 namespace quantum 中的类，以及其中的一个结构体 complex 表示复数。
Evaluator 的使用请参考checker。
Printer 的使用：可以使用带文件指针进行初始化，或者使用 set_file(FILE *file) 指定输出文件。关于输出格式中提到的所有操作，可以直接用 <对象>.<操作名> 这个函数，参数为提到的参数，控制比特默认为 0，即没有。ReturnFull 需传入正确长度的 std::vector。注意该类不会进行输出合法性检查。
Simulator 的使用：创建对象时需传入需要用到比特的个数（不能超过16，但可以自行修改maxn）。初始状态为 $|0\dots0\rangle$ ，可以进行 reset() 回到该状态（或者自行修改状态w）。可以使用所有对比特的操作，与 Printer 传参要求相同。M(uint8_t id) 会读取比特的信息，返回true 代表1，或 false 代表0，用std::mt19937 实现随机。M(uint8_t id, bool res) 会强制读取结果是 res，同时更新当前状态的概率，若成功则返回 true，否则（即概率为0）返回 false；可通过 get_probability() 读取当前概率，以及 reset_p()将概率重置为1。

参考资料

对这些东西感兴趣的可以去看看 codeforces 上以前的一些 Q# coding contest 的比赛，或者以前 WC 的课件。这道题其实没有涉及到算法，是一道送分题。