题目描述
给定非负整数 x 和一个包含 n 个非负整数的可重集 S=(a1,…,an)。若一个非空子集内,任意两个被选元素 u,v 都满足 u⊕v≤x,则称它为平衡集合,其中 ⊕ 是按位异或。单个被选元素本身可以大于 x。
求 S 的非空平衡子集个数。同一个值的不同出现位置可分别选择,下标集合不同的方案分别计数。答案对 998244353 取模。
输入格式
第一行两个整数 n,x。第二行 n 个整数 a1,…,an。
输出格式
输出一个整数,表示答案对 998244353 取模后的结果。
样例 1
4 2
0 1 2 3
8
样例 2
4 0
1 1 2 2
6
原题另在下发文件中提供样例 3–5。
数据范围
1≤n≤1.5×105,0≤ai,x<230。
| 测试点 |
n 上界 |
附加性质 |
| 1–2 |
15 |
|
| 3–4 |
1.5×105 |
x=0 |
| 5 |
x,ai<24 |
| 6 |
1.5×103 |
| 7–9 |
1.5×105 |
x+1 的二进制表示恰好有一个 1 |
| 10–12 |
每个 ai 的二进制表示恰好有一个 1 |
| 13–15 |
3000 |
|
| 16–20 |
1.5×105 |
原 PDF 题面