UOJ Logo Universal Online Judge

UOJ

#443. 【集训队作业2018】不可名状

统计

这是一道交互题

题目描述

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

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

「哈哈哈哈哈哈哈」

$\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\lt n,-2^{16}\lt k \lt 2^{16}$ 。调用该函数后,对于所有二进制第 $d$ 位为 1 的 $i$ ,令 $a'_i = x^ka_i $ 。随后 $a_i$ 更新为 $a'_i$ 。

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

$$ \begin{equation} \left\{ \begin{array}{lr} a'_{i-2^{d_2}} = A_{0,0}a_{i-2^{d_2}}+A_{1,0}a_{i} \\ a'_{i}=A_{0,1}a_{i-2^{d_2}}+A_{1,1}a_{i} \end{array} \right.\end{equation} $$

随后 $a_{i-2^{d_2}}$ 更新为 $a'_{i-2^{d_2}}$ , $a_{i}$ 更新为 $a'_{i}$ 。

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

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 。

子任务编号分值限制性质
19QR 调用次数不超过 1 次$x\in \{ -1,1\}$
217$x\in \{\omega_{8}^k \} $
336QR 调用次数不超过 1 次$x\in \{\omega_{512}^k \}$
438QR 调用次数不超过 1 次$x\in \{\omega_{65536}^k \}$

 

其中 $\omega_n $ 表示 $n$ 次单位根,$k$ 为整数。

满足 $AA^∗=I$ 的矩阵被称为酉矩阵

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

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

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

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

下载

交互库下载