← 返回题目列表

Codeforces · 1336/E2

E2. Chiori和娃娃挑选(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。简单版本和困难版本之间的唯一区别是 $$$m$$$ 的约束。只有两个版本都解决了,你才能进行黑客攻击。

Chiori 喜欢娃娃,现在她要装饰她的卧室!

作为一个娃娃收藏家,Chiori 拥有 $$$n$$$ 娃娃。第 $$$i$$$ 个娃娃具有非负整数值 $$$a_i$$$($$$a_i < 2^m$$$,给出 $$$m$$$)。 Chiori想要挑选一些(也许是零个)娃娃来装饰,所以有$$$2^n$$$不同的挑选方式。

令 $$$x$$$ 为 Chiori 选择的玩偶值的按位异或和(如果 Chiori 没有选择玩偶 $$$x = 0$$$)。该拾取方式的值等于$$$x$$$的二进制表示中的$$$1$$$位的数量。更正式地说,它也等于索引的数量 $$$0 \leq i < m$$$,因此 $$$\left\lfloor \frac{x}{2^i} \right\rfloor$$$ 是奇数。

告诉她从 $$$0$$$ 到 $$$m$$$ 的每个整数 $$$i$$$ 的值为 $$$i$$$ 的挑选方式的数量。由于答案可能非常庞大,请按模 $$$998\,244\,353$$$ 打印它们。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 53$$$) — 娃娃的数量和拾取方式的最大值。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^m$$$) — 娃娃的值。

输出

打印 $$$m+1$$$ 整数 $$$p_0, p_1, \ldots, p_m$$$  — $$$p_i$$$ 等于值为 $$$i$$$ 的拾取路数除以 $$$998\,244\,353$$$ 模。

示例

输入 #1

4 4
3 5 8 14

输出 #1

2 2 6 6 0

输入 #2

6 7
11 45 14 9 19 81

输出 #2

1 2 11 20 15 10 5 0