UOJ328 【UTR #3】量子破碎

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

$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;
}