#P13319. [2025年队测]棒棒牛轧糖

    ID: 12503 传统题 2000ms 512MiB 尝试: 6 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-线性 DP计数 DP异或 Trie

[2025年队测]棒棒牛轧糖

题目背景

距离小猫驿站联考还有 0 天,接龙哈!发给你最好的 10 个朋友,超过 15 个就永远幸福,不许在你这里断了。

今天必须发完,不许偷懒。想起谁,发给谁,包括我,别小气 ,如果我不是你的朋友,你也可以不发。

  • 传送 0 人 这也是为什么我们要抓紧时间好好学习。
  • 传送 1 人 流光容易把人抛。
  • 传送 5 人 征服世界的将是这样一些人:
  • 传送 10 人 开始的时候,他们试图找到梦想中的乐园,
  • 传送 15 人 最终,当他们无法找到时,
  • 传送 20 人 就亲自创造了它。

题目描述

椅子砸在了地上,地板裂成了 nn 块碎片;第 ii 块碎片的价值为 aia_i。

小肚可以将任意两块碎片 i,ji,j(i≠ji\neq j)放在一起,美丽度为 ai⊕aja_i\oplus a_j,即二者价值的异或和。

小肚有一个篮筐,喜爱度是非负整数 mm。小肚希望选出若干个碎片,满足他将任意两块碎片放在一起,美丽度均不小于篮筐的美 丽度,才能修复地板。

小肚希望你能帮他求出能够修复地板的选择碎片的方案数,对 998,244,353998,244,353 取模。两种方案不同当且仅当存在一个碎片在一种方 案中选择而在另外一种方案中未被选择。

形式化地,小肚需要你求出 S⊆{1,2,…,n}S\subseteq \{1,2,\dots,n\} 的 SS 个数,满足 ∀i,j∈S,i≠j\forall i,j\in S,i\neq j 有 ai⊕aj≥ma_i\oplus a_j\ge m。

输入格式

第一行一个非负整数 cc 表示测试点编号。对于样例,有 c=0c=0。

第二行一个正整数 nn 和一个非负整数 mm。

第三行 nn 个用空格隔开的非负整数 a1,a2,…,ana_1,a_2,\dots,a_n。

输出格式

输出一行一个非负整数表示答案。

输入输出样例 #1

输入 #1

0
6 0
4 1 9 4 8 7

输出 #1

64

输入输出样例 #2

输入 #2

0
6 3
4 1 9 4 8 7

输出 #2

36

说明/提示

【样例解释 #1】

所有 2n2^n 个方案都是合法的。


本题共 2020 个测试点,每个测试点 55 分,满分 100100 分。

  • 对于测试点 1∼21\sim 2:1≤n≤151\le n\le 15,0≤m≤(n2)0\le m\le \binom{n}{2};
  • 对于测试点 3∼63\sim 6:1≤n≤1001\le n\le 100;
  • 对于测试点 7∼107\sim 10:1≤n≤50001\le n\le 5000;
  • 对于测试点 11∼1411\sim 14:1≤n≤1051\le n\le 10^5;
  • 对于测试点 15∼1615\sim 16:m≤5m\le 5;
  • 对于测试点 17∼2017\sim 20:无特殊限制。

对于所有测试点,保证 1≤n≤6×1051\le n\le 6\times 10^5,0≤ai,m<2600\le a_i,m\lt 2^{60}。