← 返回题目列表

AtCoder · pakencamp_2022_day3_h

H. 恰好 K 个平方数

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

配点 : 100 点

問題文

在假设的解决方案中发现错误,因此我们将其替换为正确的解决方案并更改了问题约束。 (M \le 10^{12} 减去 M \le 10^9) 我们向受影响的人致歉。 (15:29) 一切满足

正整数 N,M 。 对于

0\leq K\leq N-1 的 对于 K ,将以下值设置为 除以 998244353 求除以后的余数。

  • 1 以上 M 长度仅由小于或等于的整数组成 N 序列 使用 A=(A_1,A_2,\ldots,A_N) 并且是,A_i \times A_{i+1} 是一个平方数。 i\,(1\leq i\leq N-1) 只是 存在 K 的事物总数 输出

制約

  • 2\leq N\leq 2000
  • 1 \le M \le 10^{9}
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M

出力

N 行。 i\, (1\leq i\leq N) 行中, K=i-1 时打印答案。


入力例 1

3 2

出力例 1

2
4
2
  • K=0 时计数 A 是 您也可以写 (1,2,1),(2,1,2) 可以得到第 2 一。 请注意,无法创建
  • K=1 时计数 A 是 您也可以写 (1,1,2),(1,2,2),(2,1,1),(2,2,1) 可以得到第 4 一。 请注意,无法创建
  • K=2 时计数 A 是 您也可以写 (1,1,1),(2,2,2) 可以得到第 2 一。 请注意,无法创建

入力例 2

7 9

出力例 2

1236360
1801104
1168800
444960
111630
17796
2319

入力例 3

10 1000000000

出力例 3

463421383
80897715
609130572
681545366
345958046
718253740
76864047
286280738
642996694
527041309