NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. 任务
  2. 2. 限制与约定
  • 题解
    1. 1. Subtask 1
    2. 2. Subtask 2
    3. 3. Subtask 3
      1. 3.1. Part1
      2. 3.2. Part2
  • Subtask 4
  • Subtask 5 & 6
  • 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从入门到放弃

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    #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;
    }

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

    本文最后更新于 天前,文中所描述的信息可能已发生改变