23639번 - Color Numbers 다국어

You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$ and an integer $k$. Two indices $i, j$ are called inconsistent if both of the two conditions hold:

1. $a_i \text{ }\mathrm{AND}\text{ } a_j = a_i$,
2. Binary representation of $(a_i \text{ }\mathrm{XOR}\text{ } a_j)$ have at least $k$ bits set to $1$.

Here $\mathrm{AND}$ stands for bitwise and operation, $\mathrm{XOR}$ stands for bitwise exclusive-OR operation.

A consistent coloring of $a_1, \ldots, a_n$ in $m$ colors is an array of $n$ integers $c_1, \ldots, c_n$ ($1 \leq c_i \leq m$) such that there is no pair of inconsistent indices $i, j$ with $c_i = c_j$.

Your task is to find the smallest possible number of colors in a consistent coloring of $a_1, \ldots, a_n$.

In the first line you are given two integers $n, k$ ($1\leq n, k\leq 5\cdot 10^5$).

In the next line you are given $n$ integers $a_i$ ($0\leq a_i < 2^{22}$).

Print one integer --- the smallest number of colors in a consistent coloring.

One possible consistent coloring in two colors is $1, 1, 1, 2$. Since indices $2$ and $4$ are inconsistent, one color is not enough.