← 返回题目列表

Codeforces · 1408/I

I. 按位魔法

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

给定一个正整数 $$$k$$$ 和一个数组 $$$a_1, a_2, \ldots, a_n$$$,其中非负不同整数不小于 $$$k$$$ 且不大于 $$$2^c-1$$$。

在接下来的每一 $$$k$$$ 秒中,从所有 $$$n$$$ 元素中随机等概率地选择一个元素,并减少 $$$1$$$。

对于每个整数 $$$x$$$, $$$0 \leq x \leq 2^c - 1$$$,您需要找到最终数组所有元素的按位异或等于 $$$x$$$ 的概率。

这些值中的每一个都可以表示为不可约分数 $$$\frac{p}{q}$$$,并且您需要找到 $$$p \cdot q^{-1}$$$ 模 $$$998\,244\,353$$$ 的值。

输入

输入的第一行包含三个整数 $$$n, k, c$$$ ($$$1 \leq n \leq (2^c - k)$$$, $$$1 \leq k \leq 16$$$, $$$1 \leq c \leq 16$$$)。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$k \leq a_i \leq 2^c-1$$$)。

输出

打印 $$$2^c$$$ 整数:$$$\{0, 1, \ldots, 2^c-1\}$$$ 模 $$$998\,244\,353$$$ 中的 $$$x$$$ 最终按位异或等于 $$$x$$$ 的概率。

示例

输入 #1

4 1 3
1 2 3 4

输出 #1

0 0 0 748683265 0 499122177 0 748683265