← 返回题目列表

Codeforces · 1716/D

D. 芯片移动

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

坐标线上有一个缺口。最初,芯片位于点$$$0$$$。您可以执行任意数量的动作;每次移动都会使芯片的坐标增加某个正整数(称为移动的长度)。您进行的第一次移动的长度应能被 $$$k$$$ 整除,第二次移动的长度可被 $$$k+1$$$ 整除,第三次移动的长度可被 $$$k+2$$$ 整除,依此类推。

例如,如果 $$$k=2$$$,则移动顺序可能如下所示: $$$0 \rightarrow 4 \rightarrow 7 \rightarrow 19 \rightarrow 44$$$,因为 $$$4 - 0 = 4$$$ 可以被 $$$2 = k$$$ 整除,$$$7 - 4 = 3$$$ 可以被 $$$3 = 整除k + 1$$$、$$$19 - 7 = 12$$$ 可以被 $$$4 = k + 2$$$ 整除、$$$44 - 19 = 25$$$ 可以被 $$$5 = k + 3$$$ 整除。

给你两个正整数 $$$n$$$ 和 $$$k$$$。你的任务是计算从 $$$0$$$ 开始,对于 [1, n]$$$ 中的每个 $$$x \ 到达点 $$$x$$$ 的方式数量。方式的数量可能非常大,因此打印它对 $$$998244353$$$ 取模。如果两种方式作为访问位置的集合不同,则被认为是不同的。

输入

输入的第一行(也是唯一的一行)包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$)。

输出

打印 $$$n$$$ 整数 - 从 $$$0$$$ 开始,对于 [1, n]$$$ 中的每个 $$$x \,到达点 $$$x$$$ 的方式数,以 $$$998244353$$$ 为模。

示例

输入 #1

8 1

输出 #1

1 1 2 2 3 4 5 6

输入 #2

10 2

输出 #2

0 1 0 1 1 1 1 2 2 2

注意

让我们看第一个例子:

到达$$$1$$$的方法:$$$[0, 1]$$$;

到达$$$2$$$的方法:$$$[0, 2]$$$;

到达$$$3$$$的方法:$$$[0, 1, 3]$$$, $$$[0, 3]$$$;

到达$$$4$$$的方法:$$$[0, 2, 4]$$$, $$$[0, 4]$$$;

到达$$$5$$$的方法:$$$[0, 1, 5]$$$, $$$[0, 3, 5]$$$, $$$[0, 5]$$$;

到达$$$6$$$的方法:$$$[0, 1, 3, 6]$$$, $$$[0, 2, 6]$$$, $$$[0, 4, 6]$$$, $$$[0, 6]$$$;

到达$$$7$$$的方法:$$$[0, 2, 4, 7]$$$, $$$[0, 1, 7]$$$, $$$[0, 3, 7]$$$, $$$[0, 5, 7]$$$, $$$[0, 7]$$$;

到达$$$8$$$的方法:$$$[0, 3, 5, 8]$$$, $$$[0, 1, 5, 8]$$$, $$$[0, 2, 8]$$$, $$$[0, 4, 8]$$$, $$$[0, 6, 8]$$$, $$$[0, 8]$$$。