给定 n 个物品,定义第 i 个物品的 特征值 为 ai,其中 ai 是整数且满足 0≤ai<2m 。
你需要选择若干物品形成一个组合。一个组合的 独特值 为其包含的物品的特征值的 异或和 。
注意,你可以一个物品也不选,此时我们认为独特值为 0 。
当你选择出一个组合后,你会邀请你的两个伙伴来挑选这些物品。
只不过,两个人只约定了一共选出 B 个物品,而忘记保证它们互不冲突,也就是说一个物品可能同时被两人选择。
请注意,一共选出 B 个物品指的是选择次数为 B,而不是被选择的物品数为 B 。
你对一个组合产生的 期待值 为两个伙伴从组合中挑选物品的本质不同方案数。
两个方案本质不同当且仅当存在一个物品,使得其在第一个方案中被某个人选择了,而在第二个方案中没有被那个人选择。
对于每个 0≤i<2m,你需要对所有独特值为 i 的组合,求出它们的期待值之和。
由于答案可能过大,你只需要输出答案对 998244353 取模的结果。
输入格式
第一行三个整数 n,m,B,意义参考题面。\ 接下来一行 n 个整数,第 i 个即 ai,意义参考题面。
输出格式
一行 2m 个整数,第 i 个数表示独特值为 i−1 的所有组合的期待值之和,对 998244353 取模后的结果。
样例输入 1
3 3 2
1 2 5
样例输出 1
0 1 1 6 6 1 15 6
样例解释 1
独特值为 3 的仅有一种组合,即选择特征值为 1 和特征值为 2 的物品。\ 此时可能的挑选方案有(我们记两个人分别为 A, B):
- A 选择两个。
- B 选择两个。
- A 选择第一个,B 同样选择第一个。
- A 选择第二个,B 同样选择第二个。
- A 选择第一个,B 选择第二个。
- A 选择第二个,B 选择第一个。
一共六种方案,因此该组合期待值为 6 。
样例输入 2 / 样例输出 2
见下发文件 ex_goods2.in / ex_goods2.ans 。
该样例约束与测试点 3∼5 一致。
样例输入 3 / 样例输出 3
见下发文件 ex_goods3.in / ex_goods3.ans 。
该样例约束与测试点 14∼17 一致。
样例输入 4 / 样例输出 4
见下发文件 ex_goods4.in / ex_goods4.ans 。
该样例约束与测试点 18∼25 一致。
数据范围
本题共 25 个测试点,每个测试点等分(即每个测试点 4 分)。
测试点编号 | n≤ | m≤ | 特殊性质 |
---|---|---|---|
1∼2 | 20 | 20 | 无。 |
3∼5 | 300 | 10 | |
6∼11 | 3000 | 20 | |
12∼13 | 106 | 保证 B=0 。 | |
14∼17 | 11 | 无。 | |
18∼25 | 20 |
对于所有数据,满足:1≤n≤106,1≤m≤20,0≤B≤n 。