[R6F]异或问题 - 代码源竞赛平台

时空限制

2S/512M

题目描述

给定整数 $X$ 和一个长度为 $n$ 的整数数组 $A$，对于 $1\sim n$ 的每个 $i$ 求有多少个 $j$ 同时满足以下三个条件：

• $i\leq j$；

• $A_i\oplus A_j> X$；

• $\text{popcount}(A_i)\leq \text{popcount}(A_j)$。

这里的 $\oplus$ 表示按位异或运算。

$\text{popcount}(V)$ 表示求 $V$ 在二进制下 $1$ 的数量，例如：$\text{popcount}(7)=3$，$\text{popcount}(16)=1$，$\text{popcount}(0)=0$。

格式

输入格式

第一行包含两个整数 $n$ 和 $X$，分别表示数组 $A$ 的长度和 $A_i\oplus A_j$ 需要大于的值。

第二行包含 $n$ 个整数 $A_i$。

输出格式

输出一行包含 $n$ 个整数，第 $i$ 个整数表示有多少个 $j$ 同时满足三个条件。

样例

样例输入 #1

6 4
3 4 7 6 8 3

样例输出 #1

1 2 0 1 1 0

样例解释 #1

对于 $i=1$，$\text{popcount}(A_1)=2$，有一个 $j$ 满足条件：$A_1\oplus A_4=5$ 且 $\text{popcount}(A_4)=2$。

对于 $i=2$，$\text{popcount}(A_2)=1$，有两个 $j$ 满足条件：$A_2\oplus A_5=12$ 且 $\text{popcount}(A_5)=1$，$A_2\oplus A_6=7$ 且 $\text{popcount}(A_6)=2$。

对于 $i=3$，$\text{popcount}(A_3)=3$，有零个 $j$ 满足条件。

对于 $i=4$，$\text{popcount}(A_4)=2$，有一个 $j$ 满足条件：$A_4\oplus A_6=5$ 且 $\text{popcount}(A_6)=2$。

对于 $i=5$，$\text{popcount}(A_5)=1$，有一个 $j$ 满足条件：$A_5\oplus A_6=11$ 且 $\text{popcount}(A_6)=2$。

对于 $i=6$，$\text{popcount}(A_6)=2$，有零个 $j$ 满足条件。

数据规模

对于 $20\%$ 的数据，$n\leq 1000$。

另有 $30\%$ 的数据，$X,A_i\leq 1000$。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$0\leq X,A_i\leq 10^9$。