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 \neq 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} b[x] = A[0][0] \cdot a[x] + A[1][0]\cdot a[x+2^i],\\ b[x+2^i] = A[0][1]\cdot a[x] + A[1][1]\cdot a[x+2^i],\end{cases} $$ 则 $a[x]$ 将更新为 $b[x]$, $a[x+2^i]$ 将更新为 $b[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 不同,不会导致数组清空开始新的一轮。
限制与约定
一共五个子任务,每个子任务有对应的分数。
每个子任务都有对应的可以使用的函数,使用了不可使用的函数会失去这个子任务的分数。
为了拿到每个子任务的分数,你必须通过所有他依赖的子任务。
所有的子任务中都不能使用超过 $400$ 个操作。
子任务 | 分值 | $n$ 的规模 | 可以使用的函数 | 依赖的子任务 |
---|---|---|---|---|
1 | 5 | $n=8$ | 1,2,3,4 | |
2 | 15 | $n=16$ | 1,2,3,4 | 1 |
3 | 20 | $n=16$ | 1,2,3 | 1,2 |
4 | 20 | $n=16$ | 1,2,4 | 1,2 |
5 | 20 | $n=6$ | 1,2 | |
6 | 20 | $n=16$ | 1,2 | 1,2,3,4,5 |
时间限制:$2s$
空间限制:256MB
题解
Subtask 1
我们看到 $n$ 较小, 我们可以直接查询每一个位置, 然后就获得了 $5$ 分的好成绩。
Subtask 2
因为每个函数只能用小于 $400$ 次, 我们考虑如何减少查询次数。
按位考虑
如果我们只想知道 $x \oplus y$ 的第 $i$ 位是否为$1$, 那么我们不用考虑其他位, 也就是说, 我们要把 $x,y$ 中除第 $i$ 位以外的位都变为 $0$。 这是一个不可逆的操作。 所以矩阵是不可逆的, 所以我们要用的操作为 $3$, 矩阵为 $\begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}$
这本质上是把第 $i$ 位为 1 的数 $x$ 累加到 $x - 2^i$ 上, 然后将 $x$ 的值设为 $0$。
最后要查询一下 $a[0]$ 与 $a[2^i]$ 是否都为 $1$。
(UPD 2018-4-25 21:37)
还有一种方法(by wq)
同样是按位考虑作用矩阵 $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$
这样作用完了之后如果 $x \oplus y$ 中有 $2^i$, 那么最后查询 $2^i$就为$\frac{1}{\sqrt{2} }$。
查询一下就好了。
20pts
Subtask 3
Part1
我们考虑如何丢掉最后一步用操作4查 $a[0]$ 和$a[2^i]$
如果直接随机,那么无论 xor 是 0 还是 1 ,都会随机返回 0 或 1 (每次 x 会重新随机)。
为了区分出来我们做变换 $a[0]=a[0]+a[2^i]$, $a[2^i]=a[0]-a[2^i]$, 用上矩阵$\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$
如果异或值为 1 则答案一定为 $0$, 否则答案为$0$或$1$。
那么我们可以多次询问搞一下。
可是并不能过掉第三个Subtask, 因为复杂度是 $n^2$ 的然后如果乘个常数, 好像就超次数了。
如果我的理解有不对的, 请联系我。
Part2
我们考虑另一种概率做法。
注意题面里有提到交互库的实现,会在概率平方和为0的时候返回0。
如果平方和不为0,返回0的概率很小。
对于每一位我们作用上 $\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$
这样如果 $x, y$ 的第 $i$ 位都为 1, 则一定会返回 $0$, 其他情况下返回$0$ 的概率很小, 基本不用考虑。
那么如果返回 $0$, 我们可以就认为$x, y$的第$i$ 位都为 1。 这种方法得出的结果是有很小的概率不对的, 但正确的概率很大。
事实上, 所有 Subtask 3 的数据都不会卡掉这个做法。
但如果 $x, y$ 的值都为 $0$, 他依然不会返回 $0$, 所以我们要多次查询, 在这些次中,有很大的概率使得有至少一次 $x, y$ 都为 1。
到此我们得到了 $40$ 分的好成绩。
Subtask 4
我们看一下Subtask 3 Part1 中的那个变换, 其实它很有用。
他本质上就是一个异或的$FWT$的正变换。
然后回顾一下他的性质, 在变换完的数组中, 下标为 $2^i$ 的位置的值为所有二进制中第 i 位不为 1 的数的和减所有二进制中第 i 位为 1 的数的和。
那么如果 $x, y$ 的二进制第 $i$ 位相同那么 $a[2^i]$ 就是 0, 反之亦然。
这样我们就能求出答案了
还有一件事, 因为要保证 $AA^T=I$, 所以我们不能用 $\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ 而是用 $\begin{pmatrix} \frac{1}{\sqrt{2} } & \frac{1}{\sqrt{2} } \\ \frac{1}{\sqrt{2} } & -\frac{1}{\sqrt{2} } \end{pmatrix}$
这样相当于将所以数都乘了一个 $\frac{1}{\sqrt{2} }^n$
这样就有 $60$ 分了。
Subtask 5 & 6
我们已经知道了他是一个$FWT$,我们考虑随机的一位对我们有用的信息是什么
考虑 $x$ 对一个数 $t$ 的贡献, 根据 $FWT$ 的定义他显然为 $(-1)^{cnt(x & t)}$, $cnt(x & t)$ 表示 $x & t$ 的二进制中 1 的个数。
如果有两个数 $x, y$ 对 $t$ 贡献, 那么贡献的值 $v$ 为 $(-1)^{cnt(x&t)} + (-1)^{cnt(y & t)}$
$v$ 不为 0 的条件是 $cnt(x & t) + cnt(y & t)$ 为奇数。
我们可以证明 $cnt(x & t) + cnt(y & t)$ 的奇偶性与 $cnt((x \oplus y) & t)$ 的奇偶性相同。
证明:
考虑没一个二进制位。
枚举 $x, y, t$ 在这一位的值, 在每一种情况下他们的奇偶性相同
$x$ $y$ $t$ $cnt(x & t) + cnt(y & t)$ $x \oplus y$ $cnt((x \oplus y) & t)$ 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 2 0 0
我们可以求出任意 $n$ 个不为 0 的位置。 如果他们是线性无关的, 那是不是就能求出 $x \oplus y$ 的值了呢?
很可惜并不是。
这些 $t$ 可能并不是满秩的!
因为所有 $x \oplus y = 0$ 始终都会是 xor 方程的解。
那怎么办呢?
有两种方法
枚举每一个不为 0 的数。 判断他是否为这个方程的解。
时间复杂度为 $O(n2^n)$, 询问次数为 $O(n^2)$。
或者:
直接高斯消元, 然后排除掉 $x \oplus y = 0$ 这个解就可以了。
时间复杂度为 $O(n^2)$, 询问次数为 $O(n^2)$
可以 AC 此题。
FWT从入门到放弃
1 |
|