309671: CF1716D. Chip Move

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Chip Move

题意翻译

给定两个数 $n,k$,问从 $0$ 开始,第 $i$ 步只能走 $(k+i-1)$ 的正倍数(即不能走 $0$),问分别走到 $x\in[1,n]$ 的方案数,对 $998244353$ 取模。

题目描述

There is a chip on the coordinate line. Initially, the chip is located at the point $ 0 $ . You can perform any number of moves; each move increases the coordinate of the chip by some positive integer (which is called the length of the move). The length of the first move you make should be divisible by $ k $ , the length of the second move — by $ k+1 $ , the third — by $ k+2 $ , and so on. For example, if $ k=2 $ , then the sequence of moves may look like this: $ 0 \rightarrow 4 \rightarrow 7 \rightarrow 19 \rightarrow 44 $ , because $ 4 - 0 = 4 $ is divisible by $ 2 = k $ , $ 7 - 4 = 3 $ is divisible by $ 3 = k + 1 $ , $ 19 - 7 = 12 $ is divisible by $ 4 = k + 2 $ , $ 44 - 19 = 25 $ is divisible by $ 5 = k + 3 $ . You are given two positive integers $ n $ and $ k $ . Your task is to count the number of ways to reach the point $ x $ , starting from $ 0 $ , for every $ x \in [1, n] $ . The number of ways can be very large, so print it modulo $ 998244353 $ . Two ways are considered different if they differ as sets of visited positions.

输入输出格式

输入格式


The first (and only) line of the input contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2 \cdot 10^5 $ ).

输出格式


Print $ n $ integers — the number of ways to reach the point $ x $ , starting from $ 0 $ , for every $ x \in [1, n] $ , taken modulo $ 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

说明

Let's look at the first example: Ways to reach the point $ 1 $ : $ [0, 1] $ ; Ways to reach the point $ 2 $ : $ [0, 2] $ ; Ways to reach the point $ 3 $ : $ [0, 1, 3] $ , $ [0, 3] $ ; Ways to reach the point $ 4 $ : $ [0, 2, 4] $ , $ [0, 4] $ ; Ways to reach the point $ 5 $ : $ [0, 1, 5] $ , $ [0, 3, 5] $ , $ [0, 5] $ ; Ways to reach the point $ 6 $ : $ [0, 1, 3, 6] $ , $ [0, 2, 6] $ , $ [0, 4, 6] $ , $ [0, 6] $ ; Ways to reach the point $ 7 $ : $ [0, 2, 4, 7] $ , $ [0, 1, 7] $ , $ [0, 3, 7] $ , $ [0, 5, 7] $ , $ [0, 7] $ ; Ways to reach the point $ 8 $ : $ [0, 3, 5, 8] $ , $ [0, 1, 5, 8] $ , $ [0, 2, 8] $ , $ [0, 4, 8] $ , $ [0, 6, 8] $ , $ [0, 8] $ .

Input

题意翻译

给定两个数 $n,k$,问从 $0$ 开始,第 $i$ 步只能走 $(k+i-1)$ 的正倍数(即不能走 $0$),问分别走到 $x\in[1,n]$ 的方案数,对 $998244353$ 取模。

Output

题目大意:
给定两个正整数 \( n \) 和 \( k \),从坐标线上的点 0 开始,每次移动增加坐标的数值,移动的长度必须是 \( k, k+1, k+2, \ldots \) 的正倍数。求到达每个 \( x \) 点 \( x \in [1, n] \) 的方案数,结果对 \( 998244353 \) 取模。

输入输出数据格式:
- 输入格式:第一行包含两个整数 \( n \) 和 \( k \) \( (1 \le k \le n \le 2 \cdot 10^5) \)。
- 输出格式:输出 \( n \) 个整数,表示到达每个 \( x \) 点 \( x \in [1, n] \) 的方案数,每个数对 \( 998244353 \) 取模。题目大意: 给定两个正整数 \( n \) 和 \( k \),从坐标线上的点 0 开始,每次移动增加坐标的数值,移动的长度必须是 \( k, k+1, k+2, \ldots \) 的正倍数。求到达每个 \( x \) 点 \( x \in [1, n] \) 的方案数,结果对 \( 998244353 \) 取模。 输入输出数据格式: - 输入格式:第一行包含两个整数 \( n \) 和 \( k \) \( (1 \le k \le n \le 2 \cdot 10^5) \)。 - 输出格式:输出 \( n \) 个整数,表示到达每个 \( x \) 点 \( x \in [1, n] \) 的方案数,每个数对 \( 998244353 \) 取模。

加入题单

上一题 下一题 算法标签: