这是一道交互题 。

题目描述

「你有一万个理由和你们队的画风不太一样

「最简单的理由：你太菜了

「哈哈哈哈哈哈哈」

$\mathfrak{rehtien}$ 和 $\mathfrak{airrats}$ 也在玩猜数游戏。

规则是这样的： $\mathfrak{rehtien}$ 先想一个数 $x$ ，然后 $\mathfrak{airrats}$ 进行猜测，如果猜对了， $\mathfrak{rehtien}$ 就会帮她出题。

但很快， $\mathfrak{airrats}$ 就意识到了问题：「你都不让我二分，我怎么猜？」因此 $\mathfrak{airrats}$ 规定 $|x|=1$ ，这样她就有 $\frac{1}{2}$ 的概率猜中了。

因此当下一轮游戏结束后， $\mathfrak{rehtien}$ 告诉她， $x\in \mathbb{C}$ ，而他想的数是 $i$ 时， $\mathfrak{airrats}$ 非常生气。她觉得有必要使用一些玄妙的方法。

任务介绍

具体地， $\mathfrak{airrats}$ 有一个长为 $2^n$ 的数组，初始 $a_0=1$ ，其余为 0 。

她要实现一个函数 SOL(t) ，其中 $t$ 为子任务编号。函数返回一个复数，表示 $x$ 。

她可以调用如下函数：

INI(n) 其中 $1\le n\le 16$ 。该函数须在调用下文的函数前调用恰一次 ，表示初始化一个长为 $2^n$ 的数组。

CU(d,k) 其中 $0\le d<n,-2^{16}<k<2^{16}$ 。调用该函数后，对于所有二进制第 $d$ 位为 1 的 $i$ ，令 $a_i^{\prime }=x^k{a}_i$ 。随后 $a_i$ 更新为 $a_i^{\prime }$ 。

CR(d1,d2,A) 其中 $0\le d_1,d_2<n$ ，$A$ 是一个 $2\times 2$ 的复数矩阵，满足 $A{A}^{\ast }=I$ ，其中 $I$ 为单位矩阵， $A^{\ast }$ 为 $A$ 的共轭转置。调用该函数后，对于所有二进制第 $d_1,d_2$ 位均为 1 的 $i$ ，令

$$\{\begin{array}{l}{a}_{i-2^{d_2}}^{\prime }=A_{0,0}{a}_{i-2^{d_2}}+A_{1,0}{a}_i\\ a_i^{\prime }=A_{0,1}{a}_{i-2^{d_2}}+A_{1,1}{a}_i\end{array}$$

随后 $a_{i-2^{d_2}}$ 更新为 $a_{i-2^{d_2}}^{\prime }$ ， $a_i$ 更新为 $a_i^{\prime }$ 。

ACR(A) 其中 $A$ 指向一个 $2^n\times 2^n$ 的复数矩阵，满足 $A{A}^{\ast }=I$ 。调用该函数后，令 $a_i^{\prime }=\sum _{j=0}^{2^n-1}{A}_{i,j}{a}_j$ ，随后 $a_i$ 更新为 $a_i^{\prime }$ 。 如果需要调用该函数，请注意时空复杂度。

QR()会随机返回一个 $[0,2^n)$ 间的整数，返回 $i$ 的概率为 $\frac{|a_i{|}^2}{\sum _j|a_j{|}^2}$ 。

实现细节

源代码需要包含头文件 unnamable.h 。

涉及到的函数接口如下：

complex<double> SOL(int t);
void INI(int n);
void CU(int d,int k);
void CR(int d1,int d2,complex<double> A[2][2]);
void ACR(complex<double> **A);
int QR();

详见样例程序 sample.cpp 。关于上述函数的具体实现，详见 grader.cpp 。

下发的 grader 将从 input.txt 中读入三个整数 $ans,seed,typ$ ，分别为本组数据的答案、随机种子和子任务编号，其中 $ans$ 表示 $x={\omega }_{65536}^{ans}$ 。运行结束后，运行结果与错误信息将会被输出至 result.txt 。

限制与约定

在每组数据中， SOL() 将会被调用一次。令 $res$ 为 SOL() 的返回值， 当 $|res-x|\le {10}^{-5}$ 时视为正确。

对于所有数据，CU,CR,QR,ACR 的总调用次数不能超过 300 。

其中 ${\omega }_n$ 表示 $n$ 次单位根，$k$ 为整数。

满足 $A{A}^{\ast }=I$ 的矩阵被称为酉矩阵。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{256MB}}$

选手程序与交互库共享本题的时空限制，但由于 ACR 操作的存在，我们不能保证交互库的运行时间。最终评测使用的交互库（只保证）各函数的实现方式与下发的 grader 相同，请自行计算实际运行时间与内存。

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

下载

交互库下载