← 返回题目列表

AtCoder · xmascon24_f

F. 有限现场训练

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

配点 : 100 点

????“2024 年当时的日本,nim 的实现似乎大家都很了解,而且也经常看到使用哈希解法等在题目中没有直接出现的 nimber,但计数问题主要还是在 \mathbb{F} _ {998244353} 中进行,像这份史料中作为赋予组合对象的权重而选择 \mathbb{F} _ {2^{64}} 的出题几乎没有出现过

問題文

非負整数 n, m , 定义n 頂点 m 边带标签的简单二部图的个数记为 B(n, m) (带标签是指n 个顶点是可区分的)。

非負整数 N 和A \in \mathbb{F}_{2^{64}} 已知。每个 n = 0, 1, \ldots, N , 定义g_n = \displaystyle\sum _ {m\ge0} B(n, m) A^m 。

在这个问题的输入输出中,\mathbb{F}_{2^{64}} 的元素用 0 以上 2^{64} 它是 nimber 表示。也就是说,对于 g_n 是B(n, m) 为奇数的 m ,m 的 您可以创建一个包含 A 的 nim 乘积进行总 XOR。

制約

  • 0 \le N \le 10^6.
  • A \in \mathbb{F}_{2^{64}}.

入力

输入是按以下格式从标准输入给出的。A 以 nimber 的形式表示。

N A

出力

按以下格式输出您的答案。g_0, g_1, \ldots, g_N 以 nimber 的形式表示。 在

g_0 g_1 \cdots g_N

入力例 1

5 8

出力例 1

1 1 9 4 6 12

n \le 5 的范围内, B(n, m) 为奇数发生在 (n, m) = (0, 0), (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 2), (4, 4), (5, 0), (5, 2) 时,因此得到

  • g_0 = A^0
  • g_1 = A^0
  • g_2 = A^0 + A^1
  • g_3 = A^0 + A^1 + A^2
  • g_4 = A^0 + A^2 + A^4
  • g_5 = A^0 + A^2

(注意这些是 \mathbb{F}_{2^{64}} 中的运算)。

A^0, A^1, A^2, A^3, A^4 的 nimber 分别在 1, 8, 13, 14, 10 变为。


入力例 2

16 18446744073709551615

出力例 2

1 1 18446744073709551614 7156334549604198409 5893837254661243073 11290409524105353206 1851073793877042652 6387559487065781530 10238440391911562788 4437985372483032842 7848075886096899333 1584478287860827173 12600881811381958477 3270981160664397218 17529507309351360274 100266085651560874 1725589564589995945