#P18274. The Mysterious Shop

The Mysterious Shop

The Mysterious Shop

瓦洛兰大陆之外有一家神秘商店,没有人知道店主是谁。每天刚开始时,商店中的物品都会重新随机生成。可能出现的物品重量分别为 1,2,…,n1,2,\ldots,n:对于每一种重量,都独立地以 12\frac12 的概率出现恰好一件该重量的物品,否则没有该重量的物品。重新生成后,前一天的物品也不会保留。

初来乍到的 Kevin 想先买些好装备。他每天带着容量为 nn 的口袋,第一个走进商店,按照如下策略购买:

按重量从大到小依次检查当天商店中的物品。如果某件物品放入口袋后,总重量不超过 nn,就买下并放入口袋;否则跳过这件物品。一直检查到所有物品都已考虑。

由于当地特殊的付款方式,可以认为 Kevin 总能付得起他决定放入口袋的所有物品。

Kevin 想知道自己每天的运气如何。请对每个 i=0,1,…,ni=0,1,\ldots,n,计算一天内他最终带走物品的总重量恰好为 ii 的概率。

输入格式

输入只有一行,一个整数 nn(1≤n≤2×1051\le n\le2\times10^5),同时表示最大可能物品重量和口袋容量。

本题只有一个测试用例,输入开头没有测试用例数。

输出格式

输出一行,共 n+1n+1 个整数。第 i+1i+1 个整数表示最终带走总重量恰好为 ii 的概率乘以 2n2^n 后,对 998244353998244353 取模的结果。

可以证明,在取模之前这些值都是整数。等价地,输出 2n2^n 种等可能的商店物品集合中,分别有多少种使 Kevin 带走总重量 0,1,…,n0,1,\ldots,n,再对 998244353998244353 取模。

样例 1

输入:

1

输出:

1 1

样例 2

输入:

2

输出:

1 1 2

样例 3

输入:

3

输出:

1 1 1 5

样例 4

输入:

10

输出:

1 1 1 2 2 3 5 13 45 180 771

样例说明

第二个样例 n=2n=2 有四种等可能的商店物品集合:

商店中的物品重量集合 Kevin 带走的物品重量集合 总重量
∅\varnothing 0
{1}\{1\} 1
{2}\{2\} {2}\{2\} 2
{1,2}\{1,2\}

因此,最终总重量为 0,1,20,1,2 的概率依次是 14,14,12\frac14,\frac14,\frac12。乘以 22=42^2=4 后,输出为 1 1 2。