配点 : 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