На координатной прямой лежит фишка. Изначально фишка находится в точке $$$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$$$. Ваша задача — посчитать количество способов попасть в точку $$$x$$$, начиная из точки $$$0$$$, для всех $$$x \in [1, n]$$$. Количество способов может быть очень большим, поэтому выведите его по модулю $$$998244353$$$. Два способа считаются различными, если они отличаются как наборы посещенных позиций.
Единственная строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).
Выведите $$$n$$$ целых чисел — количество способов попасть из $$$0$$$ в точку $$$x$$$ для всех $$$x \in [1, n]$$$, взятое по модулю $$$998244353$$$.
8 1
1 1 2 2 3 4 5 6
10 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]$$$.
Название |
---|