AT_abc252_h [ABC252Ex] K-th beautiful Necklace

题目描述

有 $N$ 个宝石。第 $i$ 个宝石的颜色为 $D_i$，美丽度为 $V_i$。
其中，颜色是 $1,2,\ldots,C$ 中的某一个，并且每种颜色的宝石至少有 $1$ 个。

从 $N$ 个宝石中，选择 $C$ 个颜色各不相同的宝石来制作项链。（选择的顺序不计入考虑。）
项链的美丽度为所选宝石美丽度的按位 $\rm XOR$。

请你求出所有可能制作项链的方法中，美丽度第 $K$ 大的项链的美丽度是多少。（如果有多种制作方法得到相同的美丽度，则这些方法都计数。）

按位 $\rm XOR$ 的定义如下：
对于整数 $A, B$，按位 $\rm XOR$，即 $A\ {\rm XOR}\ B$，定义为：

• $A\ {\rm XOR}\ B$ 的二进制表示中，第 $2^k$ 位（$k\geq 0$）的数，如果 $A, B$ 的二进制表示中该位只有一个为 $1$，则为 $1$，否则为 $0$。

例如，$3\ {\rm XOR}\ 5 = 6$（二进制表示为：$011\ {\rm XOR}\ 101 = 110$）。

输入格式

输入按以下格式从标准输入读入。

$N$ $C$ $K$
$D_1$ $V_1$
$\vdots$
$D_N$ $V_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4 2 3
2 4
2 6
1 2
1 3

输出 #1

5

输入输出样例 #2

输入 #2

3 1 2
1 0
1 0
1 0

输出 #2

0

输入输出样例 #3

输入 #3

10 3 11
1 414213562373095048
1 732050807568877293
2 236067977499789696
2 449489742783178098
2 645751311064590590
2 828427124746190097
3 162277660168379331
3 316624790355399849
3 464101615137754587
3 605551275463989293

输出 #3

766842905529259824

说明/提示

限制条件

• $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$ 种项链
• 输入中的所有值均为整数

样例解释 1

可以制作如下 $4$ 种项链：

• 选择第 $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$。

样例解释 2

可以制作 $3$ 种项链，且它们的美丽度均为 $0$。

由 ChatGPT 4.1 翻译