#P9786. 平衡集合

    ID: 6416 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-异或 Trie分治算法计数 DP

平衡集合

题目描述

给定非负整数 xx 和一个包含 nn 个非负整数的可重集 S=(a1,…,an)S=(a_1,\ldots,a_n)。若一个非空子集内,任意两个被选元素 u,vu,v 都满足 u⊕v≤xu\oplus v\le x,则称它为平衡集合,其中 ⊕\oplus 是按位异或。单个被选元素本身可以大于 xx。

求 SS 的非空平衡子集个数。同一个值的不同出现位置可分别选择,下标集合不同的方案分别计数。答案对 998244353998244353 取模。

输入格式

第一行两个整数 n,xn,x。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出一个整数,表示答案对 998244353998244353 取模后的结果。

样例 1

4 2
0 1 2 3
8

样例 2

4 0
1 1 2 2
6

原题另在下发文件中提供样例 3–5。

数据范围

1≤n≤1.5×1051\le n\le1.5\times10^5,0≤ai,x<2300\le a_i,x<2^{30}。

测试点 nn 上界 附加性质
1–2 15
3–4 1.5×1051.5\times10^5 x=0x=0
5 x,ai<24x,a_i<2^4
6 1.5×1031.5\times10^3
7–9 1.5×1051.5\times10^5 x+1x+1 的二进制表示恰好有一个 11
10–12 每个 aia_i 的二进制表示恰好有一个 11
13–15 3000
16–20 1.5×1051.5\times10^5

原 PDF 题面