UOJ328 【UTR #3】量子破碎

Author Avatar
WildRage 4月 21, 2018
  • 在其它设备中阅读本文章

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

UOJ328

题解

Subtask 1

我们看到 $n$ 较小, 我们可以直接查询每一个位置, 然后就获得了 $5$ 分的好成绩。

5pts

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$。

20pts

(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$ 分的好成绩。

40pts

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$ 分了。

60pts

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从入门到放弃

#include "quantumbreak.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
double q = sqrt(0.5);
double C[2][2] = {{q, q}, {q, -q}};
vector<int> vc;
int Num(unsigned int x)
{
    unsigned int tmp = x
                     - ((x >> 1) & 033333333333)
                     - ((x >> 2) & 011111111111);
    tmp = (tmp + (tmp >> 3)) & 030707070707;
    return tmp % 63;
}
int query_xor(int n, int t)
{
    int ans = 0;
    for (int j = 0; j <= 20; j++)
    {
        for (int i = 0; i < n; i++)
            manipulate(C, i);
        vc.push_back(query());
    }
    // for (auto x : vc)
        // printf ("%d\n", x);
    for (int i = 1; i < (1 << n); i++)
    {
        bool flag = 0;
        for (auto x : vc)
        {
            // if (i == 42163) printf ("%d\n", Num(x & i));
            if (Num(x & i) & 1)
            {
                flag = 1;
                break;
            }
        }
        if (!flag) return i;
    }
    // printf ("%d\n", ans);
    return 0;
}

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接:https://blog.wildrage.xyz/2018/04/21/149/