102527: [AtCoder]ABC252 Ex - K-th beautiful Necklace
Description
Score : $600$ points
Problem Statement
We have $N$ gemstones. The color and beauty of the $i$-th gemstone are $D_i$ and $V_i$, respectively.
Here, the color of each gemstone is one of $1, 2, \ldots, C$, and there is at least one gemstone of each color.
Out of the $N$ gemstones, we will choose $C$ with distinct colors and use them to make a necklace. (The order does not matter.) The beautifulness of the necklace will be the bitwise $\rm XOR$ of the chosen gemstones.
Among all possible ways to make a necklace, find the beautifulness of the necklace made in the way with the $K$-th greatest beautifulness. (If there are multiple ways with the same beautifulness, we count all of them.)
What is bitwise $\rm XOR$?
The bitwise $\rm XOR$ of integers $A$ and $B$, $A \oplus B$, is defined as follows:
- When $A \oplus B$ is written in base two, the digit in the $2^k$'s place ($k \geq 0$) is $1$ if either $A$ or $B$, but not both, has $1$ in the $2^k$'s place, and $0$ otherwise.
Constraints
- $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}$
- There are at least $K$ ways to make a necklace.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $C$ $K$ $D_1$ $V_1$ $\vdots$ $D_N$ $V_N$
Output
Print the answer.
Sample Input 1
4 2 3 2 4 2 6 1 2 1 3
Sample Output 1
5
There are four ways to make a necklace, as follows.
- Choose the $1$-st and $3$-rd gemstones to make a necklace with the beautifulness of $4\ {\rm XOR}\ 2 =6$.
- Choose the $1$-st and $4$-th gemstones to make a necklace with the beautifulness of $4\ {\rm XOR}\ 3 =7$.
- Choose the $2$-nd and $3$-rd gemstones to make a necklace with the beautifulness of $6\ {\rm XOR}\ 2 =4$.
- Choose the $2$-nd and $4$-th gemstones to make a necklace with the beautifulness of $6\ {\rm XOR}\ 3 =5$.
Thus, the necklace with the $3$-rd greatest beautifulness has the beautifulness of $5$.
Sample Input 2
3 1 2 1 0 1 0 1 0
Sample Output 2
0
There are three ways to make a necklace, all of which result in the beautifulness of $0$.
Sample Input 3
10 3 11 1 414213562373095048 1 732050807568877293 2 236067977499789696 2 449489742783178098 2 645751311064590590 2 828427124746190097 3 162277660168379331 3 316624790355399849 3 464101615137754587 3 605551275463989293
Sample Output 3
766842905529259824
Input
题意翻译
给定 $ n $ 个珠子，每个珠子的颜色为 $ d_i $，权值为 $ v_i $。颜色共有 $ c $ 种，且保证每种颜色至少有一颗珠子。你需要从 $ n $ 个珠子种选择 $ c $ 个颜色不同的珠子串成一条项链，其权值为其中所有珠子权值的异或和。你需要输出权值第 $ k $ 大的项链的权值。只要选取的珠子不同，即使权值相同也算不同项链。数据保证可能构成的项链数不小于 $ k $。Output
得分：$600$分
问题描述
我们有$N$颗宝石。第$i$颗宝石的颜色和美丽程度分别是$D_i$和$V_i$。
其中，每颗宝石的颜色是$1, 2, \ldots, C$中的一个，每种颜色至少有一颗宝石。
从$N$颗宝石中，我们会选择颜色不同的$C$颗宝石用来制作一条项链。（顺序无关紧要。） 项链的美丽程度将是所选宝石的位异或。
在所有可能的制作项链的方法中，找出美丽程度第$K$大的项链的美丽程度。（如果有多条项链具有相同的美丽程度，我们计算所有的项链。）
什么是位异或？
整数$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$条项链。
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$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
有四种制作项链的方法，如下所示。
- 选择第$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 1 2 1 0 1 0 1 0
样例输出2
0
有三种制作项链的方法，它们的美丽程度都是$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