QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+10]
统计

给定 n 个物品,定义第 i 个物品的 特征值ai,其中 ai 是整数且满足 0ai<2m

你需要选择若干物品形成一个组合。一个组合的 独特值 为其包含的物品的特征值的 异或和

注意,你可以一个物品也不选,此时我们认为独特值为 0

当你选择出一个组合后,你会邀请你的两个伙伴来挑选这些物品。

只不过,两个人只约定了一共选出 B 个物品,而忘记保证它们互不冲突,也就是说一个物品可能同时被两人选择。

请注意,一共选出 B 个物品指的是选择次数为 B,而不是被选择的物品数为 B

你对一个组合产生的 期待值 为两个伙伴从组合中挑选物品的本质不同方案数。

两个方案本质不同当且仅当存在一个物品,使得其在第一个方案中被某个人选择了,而在第二个方案中没有被那个人选择。

对于每个 0i<2m,你需要对所有独特值为 i 的组合,求出它们的期待值之和。

由于答案可能过大,你只需要输出答案对 998244353 取模的结果。

输入格式

第一行三个整数 n,m,B,意义参考题面。\ 接下来一行 n 个整数,第 i 个即 ai,意义参考题面。

输出格式

一行 2m 个整数,第 i 个数表示独特值为 i1 的所有组合的期待值之和,对 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 。

该样例约束与测试点 35 一致。

样例输入 3 / 样例输出 3

见下发文件 ex_goods3.in / ex_goods3.ans 。

该样例约束与测试点 1417 一致。

样例输入 4 / 样例输出 4

见下发文件 ex_goods4.in / ex_goods4.ans 。

该样例约束与测试点 1825 一致。

数据范围

本题共 25 个测试点,每个测试点等分(即每个测试点 4 分)。

测试点编号 n m 特殊性质
12 20 20 无。
35 300 10
611 3000 20
1213 106 保证 B=0
1417 11 无。
1825 20

对于所有数据,满足:1n106,1m20,0Bn