P10857 【MX-X2-T6】「Cfz Round 4」Ad-hoc Master

原题链接：。 --- 意気込むことはないけれど 尽管不会每天干劲十足 生きていけるよ　君をさがして 但我会继续一边寻找着你一边生活

给定一个正整数 $h$。我们令 $n=2^h-1$。 现给出对于每个不大于 $n$ 的正整数 $u$ 和不大于 $2h-2$ 的正整数 $k$ 所对应的 $f_{u,k}$ 的值，你需要构造一组数对 $(r,w)$，满足 $1 \le r \le n$，$0 \le w \lt 2^{30}$，且存在一棵层数为 $h$ 的**满**二叉树 $T$ 满足： - 满二叉树 $T$ 中所有结点的编号形成 $1 \sim n$ 的一个排列，且每个结点都有权值； - 满二叉树 $T$ 的根结点为结点 $r$； - 满二叉树 $T$ 中每个结点的权值都为小于 $2^{30}$ 的非负整数，且根结点的权值为 $w$； - 对于每个不大于 $n$ 的正整数 $u$ 和不大于 $2h-2$ 的正整数 $k$，所有满足 $\operatorname{dis}(u,v)=k$ 的结点 $v$ 的权值的**异或和**为 $f_{u,k}$；特殊地，若没有满足条件的结点 $v$，则需要满足 $f_{u,k}=0$。 其中，$\operatorname{dis}(u,v)$ 的值等于结点 $u$ 和结点 $v$ 之间的简单路径所包含的边的数量。特殊地，$\operatorname{dis}(u,u)=0$。 题目保证至少存在一组满足条件的数对 $(r,w)$。

无

无

**【样例解释 #1】** 对于第一组测试数据： 当构造的数对 $(r,w)=(2,1)$ 时，存在一棵如图所示的二叉树符合题意，其中结点 $1,2,3$ 的权值分别为 $2,1,0$。  当你输出 `2 2` 时，你可以获得该测试点 $50\%$ 的分数，因为 $(r,w)=(2,2)$ 虽然不满足条件，但存在一组满足条件的数对 $(r',w')=(2,1)$ 满足 $r'=r=2$。 当你输出 `1 1` 时，你也可以获得该测试点 $50\%$ 的分数。 但当你输出 `1 2` 时，你将不能获得该测试点的分数。 **【数据范围】** 设 $\sum n$ 表示单个测试点中 $n$ 的和。 对于所有测试数据，$1\le T \le 1000$，$2 \le h \le 16$，$\sum n \le 2^{16}$，$0 \le f_{u,k}\lt2^{30}$，保证至少存在一组满足条件的数对 $(r,w)$。 **本题采用捆绑测试。** - Subtask 1（20 points）：$h=2$。 - Subtask 2（20 points）：满足特殊性质。 - Subtask 3（60 points）：无特殊限制。 特殊性质：存在一组数对 $(r,w)$，满足 $1 \le r \le n$，$0 \le w \lt 2^{30}$，且在此基础上存在一棵符合题意的满二叉树，其所有结点的权值均为 $w$。