UOJ Logo Universal Online Judge

UOJ

#328. 【UTR #3】量子破碎

统计

Scape下载了好久终于下完了关于量子巧克力的游戏——Quantum break,准备邀请Mythological来享受在一起的时光。可是谁知道积劳成疾的Scape,居然在Mythological到来之前就陷入了梦境之中。

Scape在梦境中隐隐约约看见了这样的一份题面:

Mythological应邀来和他一起隔膜,并且带来了一盒与游戏中同款的 ”黎明前就会破碎的量子巧克力“。

在游戏里量子巧克力可以看做一个数组 $a$,长度为 $2^n$,下标从 $0$ 开始到 $2^n-1$ 结束。

他们俩可以关于这些量子巧克力,向游戏做一些询问,但是不幸有的询问会导致量子破碎,此时游戏会刷新这个数组开始新的一轮....

即使是在梦中,Scape也想让Mythological开心,请你帮一帮他。

任务

每轮游戏开始的时候数组里只有 $a[x]=a[y]=\frac{1}{\sqrt{2}}$($x \ne y$),剩下的元素都是 $0$。

你需要编写一个函数和交互库进行多轮交互,求出 $x \oplus y$ 的值(每轮中 $x \oplus y$ 不变):

  • query_xor(n, t);
    • n 表示 a 的长度是 $2^n$,t 表示子任务编号。
    • 你的返回值是 $x \oplus y$ 的答案。

你可以通过四种操作来确定这个值:

  • query();
    • 向交互库做一次询问。
    • 交互库会随机返回一个下标,具体来说返回 $x$ 的概率恰好是 $\frac{a[x]^2}{\sum_i a[i]^2}$。
    • 返回 $x$ 之后,会开始新的一轮,交互库重新随机一对 $x$ 和 $y$ 保证 $x \oplus y$ 不变(在所有满足条件的 $x,y$ 中等概率随机,有可能不变),然后重新给数组 $a$ 赋值,使得数组里只有 $a[x]=a[y]=\frac{1}{\sqrt{2}}$($x \ne y$),剩下的元素都是 $0$。
  • manipulate(A, i);
    • 向交互库做一次操作,给出一个 $2 \times 2$ 的实数矩阵 $A$。
    • 交互库会把数组 $a$ 更新,具体来说,对于每个二进制第 $i$($i$ 是传入的参数)位为 $0$ 的数 $x$,令$$\begin{cases}a'[x] = A[0][0]\cdot a[x] + A[1][0]\cdot a[x+2^i],\\a'[x+2^i] = A[0][1]\cdot a[x] + A[1][1]\cdot a[x+2^i],\end{cases}$$则 $a[x]$ 将更新为 $a'[x]$,$a[x+2^i]$ 将更新为 $a'[x+2^i]$。
    • 为了保证 $a[x]^2$ 的和 (概率和) 始终为1,你的矩阵必须满足 $AA^T=I$,可以证明此时 $a[x]^2$ 的和始终不变($A^T$ 表示 $A$ 的转置,$I$ 为单位矩阵)。
  • arbitary_manipulate(A, i);
    • 和 manipulate 不同的是,这里不强制 $AA^T=I$。
    • 使用了这个函数后,$\sum a[x]^2$ 可能不为 $1$,询问的时候概率按照 $a[x]^2$ 的比例平均分配。
    • 如果 $\sum a[x]^2 = 0$,交互库会返回 0。(请选手使用下发的 grader 判断自己程序的精度问题)
  • arbitary_query(x);
    • 询问 a[x] 为多少。
    • 和 query 不同,不会导致数组清空开始新的一轮。

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现如上所述的 query_xor 函数,并且遵循下面的命名和接口。你需要包含头文件 quantumbreak.h。

int query_xor(int n, int t);

函数 query, manipulate, arbitary_manipulate, arbitary_query 的接口信息如下。

int query();
void manipulate(double A[][2], int i);
void arbitary_manipulate(double A[][2], int i);
double arbitary_query(int x);

如果有不清楚的地方,见样例及测评库下载,内附了样例程序,样例程序按照样例一的解释调用函数

评测方式

评测系统将读入如下格式的输入数据:

第一行三个整数 $n$,$seed$,$t$ 分别是这组测试数据的大小、随机种子和子任务编号。

第二行四个整数 $ok[1], ok[2], ok[3], ok[4]$,$ok[i] = 0$ 表示函数 $i$ 在这个子任务不可使用,$ok[i] = 1$ 表示可以使用。

限制与约定

一共五个子任务,每个子任务有对应的分数。

每个子任务都有对应的可以使用的函数,使用了不可使用的函数会失去这个子任务的分数。

为了拿到每个子任务的分数,你必须通过所有他依赖的子任务。

所有的子任务中都不能使用超过 $400$ 个操作。

子任务分值$n$ 的规模可以使用的函数依赖的子任务
15$n = 8$1, 2, 3, 4
215$n = 16$1, 2, 3, 41
320$n = 16$1, 2, 31, 2
420$n = 16$1, 2, 41, 2
520$n = 6$1, 2
620$n = 16$1, 21, 2, 3, 4, 5

交互式类型的题目怎么本地测试

时间限制:$2\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载