QOJ.ac

QOJ

Total points: 100 Output Only
[-14]

# 5172. 序程来未

Statistics

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

题目背景

在 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> 二进制下 2i 位为 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>] EndifM <id><id> 为编号。其中 IfM 为分支结构,若读取到 1 则会执行 IfM 与与它匹配的 Else(若无 Else 则为 Endif)之间的语句,否则若有匹配的 Else 的话,会执行 ElseEndif 之间的语句。如果使用 M 则会记录此时的结果并继续执行。注意:IfM 语句块中不允许使用 M

一个代码块可以有返回值,可以为 2312311 之间的任意值,默认为 0。可使用 Return <ret>,则会立刻结束这个代码块,并且返回 ret。也可以使用 ReturnFull <ret0> <ret1> ... <ret2^k-1>,共 2k 个值,其中 k 为这个代码块从 Begin 到目前为止的 M 的个数,若 M 得到的读取结果分别为 x0,x1,,xk1,则会返回第 k1i=02ixi(从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。以下非大小关系的概率误差不允许超过 106;要求的状态与生成的可以相差一个 eiθ(常数倍),且可以有 106 的绝对误差(具体参考 checker.cpp 的实现,但一般实现不回超过);若不为固定的输入,要求生成特定的输出,则要求相差的 eiθ 对所有输入均为一个常数。

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

样例1

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

任务1

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

任务2

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

任务3

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

任务4

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

任务5

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

任务6

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

任务7

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

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

任务8

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

任务9

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

任务10

1 个代码块,2 个比特,初始状态为 |00,生成 (|10|01)/2
限制:这个代码块中语句个数不超过 5,不允许使用 IfM M Rx Ry Rz

任务11

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

任务12

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

任务13

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

任务14

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

任务15

1 个代码块,6 个比特,初始状态为 |000000。生成 (|111000+|110100++|000111)/20。(含有所有含 3 个 1 的。)
限制:这个代码块中语句个数不超过 35,不允许使用 IfM M

任务16

1 个代码块,4 个比特,要求对一个系数,如果它的基向量的第0、1、2位有奇数个比特为1,则将第3位取反(0变1,1变0)。即把 |x0x1x2x3 的系数变为 |x0x1x2(x3xor[x0,x1,x2中有奇数个1]) 的系数。
限制:这个代码块中语句个数不超过 5,不允许使用 IfM M

任务17

1 个代码块,5 个比特,要求对一个系数,如果它的基向量的第0、1、2、3位恰有1个比特为1,则将第4位取反(0变1,1变0)。即把 |x0x1x2x3x4 的系数变为 |x0x1x2x3(x4xor[x0,x1,x2,x3中恰有一个1]) 的系数。
限制:这个代码块中语句个数不超过 10,不允许使用 IfM M

任务18

2 个代码块,2 个比特。初始状态为 (|00|01)/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。先执行第1个代码块,然后分别执行三个代码块,实现三个随机数生成器,三个代码块返回值为 0 或 1,且一共返回奇数个 1,且四种情况等概率。
限制:第1个代码块中语句个数不超过 4,其余代码块中语句个数不超过 2,均不允许使用 IfM;第1个代码块不允许使用 M,其余代码块至多使用 1 个 M。第2个代码块只能使用第0个比特,第3个代码块只能使用第1个比特,第4个代码块只能使用第2个比特。

任务20

5 个代码块,2 个比特,初始状态为 |00。先执行第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 的输入检测,所以可能这里能过,但不能通过上面的测试。通常只要输出中整数不会造成读入时溢出、小数按正常写法(不按科学计数法、无 naninf)就不会造成误判。

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

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

在这个模型当中,若它有 n 个比特,则(可以看作)它的内部有 2n 个复数参数 w0,w1,w2n1,可以表示这个模型的一个状态。为了方便,可以把这 2n 个参数写成一个列向量,而这个列向量的第 i 个(标准)基向量通常记作 |x0xn1,其中 i=n1k=02kxk

对单个比特的操作:一种操作对应一种酉矩阵U(它的共轭转置是它的逆),其中 H=12[1111],T=[100eiπ/4],X=[0110],Y=[0ii0],Z=[1001], Rx(θ)=[cos(θ/2)isin(θ/2)isin(θ/2)cos(θ/2)],Ry(θ)=[cos(θ/2)sin(θ/2)sin(θ/2)cos(θ/2)],Rz(θ)=[eiθ/200eiθ/2].

当它作用于第 i 个比特时,状态会发生变化 ww,具体地, [w|x0xi10xi+1xn1w|x0xi11xi+1xn1]=U[w|x0xi10xi+1xn1w|x0xi11xi+1xn1]

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

对于交换,可看成 SWAPij=[1000001001000001]

关于控制比特:当有控制比特时,我们会只对控制比特全为1的那些基向量所对应的系数进行操作。其中被操作的比特不能是控制比特。例如当一共 2 个比特时,直接对0比特操作 X 可以看作 [0100100000010010] 若第1个比特是控制比特,则矩阵可以看作 [1000010000010010]

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

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

附录2:下发文件说明

注:若需更改,更改前建议备份。

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

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

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

quantum.cppquantum.h 为库文件。里面包含模拟器 Simulator,执行器 Evaluator,以及打印输出文件的工具 Printer,均为命名空间 namespace quantum 中的类,以及其中的一个结构体 complex 表示复数。
Evaluator 的使用请参考checker。
Printer 的使用:可以使用带文件指针进行初始化,或者使用 set_file(FILE *file) 指定输出文件。关于输出格式中提到的所有操作,可以直接用 <对象>.<操作名> 这个函数,参数为提到的参数,控制比特默认为 0,即没有。ReturnFull 需传入正确长度的 std::vector。注意该类不会进行输出合法性检查。
Simulator 的使用:创建对象时需传入需要用到比特的个数(不能超过16,但可以自行修改maxn)。初始状态为 |00 ,可以进行 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 的课件。这道题其实没有涉及到算法,是一道送分题。


or upload files one by one: