AT_abc252_h.[ABC252Ex] K-th beautiful Necklace

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $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
```
4 2 3
2 4
2 6
1 2
1 3
```
输出#1
```
5
```
输入#2
```
3 1 2
1 0
1 0
1 0
```
输出#2
```
0
```

输入#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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页