#AT2180. Ex - K-th beautiful Necklace
Ex - K-th beautiful Necklace
当前没有测试数据。
Ex - 第K美丽的项链
分数：$600$ 分
题目描述
有 $N$ 个宝石。第 $i$ 个宝石的颜色和美丽度分别为 $D_i$ 和 $V_i$。
这里，每个宝石的颜色是 $1, 2, \ldots, C$ 中的一个，并且每种颜色至少有一个宝石。
在所有 $N$ 个宝石中，我们将选择 $C$ 个不同颜色的宝石，并使用它们制作一条项链。 （顺序无关紧要。） 项链的美丽度将是选择的宝石的按位 $\rm XOR$。
在所有可能制作项链的方式中，找出制作项链的方式中，第 $K$ 美丽度最高的项链的美丽度。（如果有多种美丽度相同的方式，我们计算所有这些方式。）
什么是按位异或（bitwise XOR）？
整数 $A$ 和 $B$ 的按位异或，记为 $A \oplus B$，定义如下：
- 当 $A \oplus B$ 用二进制表示时，$2^k$ 位（$k \geq 0$）上的数字为 $1$，如果 $A$ 或 $B$ 中只有一者在 $2^k$ 位上为 $1$，否则为 $0$。
约束条件
- $1 \leq C \leq N \leq 70$
- $1 \leq D_i \leq C$
- $0 \leq V_i < 2^{60}$
- $1 \leq K \leq 10^{18}$
- 有至少 $K$ 种制作项链的方式。
- 所有输入值都是整数。
输入
从标准输入中按以下格式给定：
输出
输出答案。
4 2 3
2 4
2 6
1 2
1 3
5
有四种制作项链的方式，如下所示。
- 选择第 $1$ 和第 $3$ 个宝石制作美丽度为 $4\ {\rm XOR}\ 2 =6$ 的项链。
- 选择第 $1$ 和第 $4$ 个宝石制作美丽度为 $4\ {\rm XOR}\ 3 =7$ 的项链。
- 选择第 $2$ 和第 $3$ 个宝石制作美丽度为 $6\ {\rm XOR}\ 2 =4$ 的项链。
- 选择第 $2$ 和第 $4$ 个宝石制作美丽度为 $6\ {\rm XOR}\ 3 =5$ 的项链。
因此，第 $3$ 个美丽度最高的项链的美丽度为 $5$。
3 1 2
1 0
1 0
1 0
0
有三种制作项链的方式，所有方式的美丽度均为 $0$。
10 3 11
1 414213562373095048
1 732050807568877293
2 236067977499789696
2 449489742783178098
2 645751311064590590
2 828427124746190097
3 162277660168379331
3 316624790355399849
3 464101615137754587
3 605551275463989293
766842905529259824