[dp优化]Chip Move Codeforces1716D

There is a chip on the coordinate line. Initially, the chip is located at the point 00. 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 kk, the length of the second move — by k+1k+1, the third — by k+2k+2, and so on.

For example, if k=2k=2, then the sequence of moves may look like this: 0→4→7→19→440→4→7→19→44, because 4−0=44−0=4 is divisible by 2=k2=k, 7−4=37−4=3 is divisible by 3=k+13=k+1, 19−7=1219−7=12 is divisible by 4=k+24=k+2, 44−19=2544−19=25 is divisible by 5=k+35=k+3.

You are given two positive integers nn and kk. Your task is to count the number of ways to reach the point xx, starting from 00, for every x∈[1,n]x∈[1,n]. The number of ways can be very large, so print it modulo 998244353998244353. Two ways are considered different if they differ as sets of visited positions.

Input

The first (and only) line of the input contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105).

Output

Print nn integers — the number of ways to reach the point xx, starting from 00, for every x∈[1,n]x∈[1,n], taken modulo 998244353998244353.

Examples

input

8 1

output

1 1 2 2 3 4 5 6 

input

10 2

output

0 1 0 1 1 1 1 2 2 2 

题意： 有n个点顺序排列在1~n，起点在0，第i次跳跃的距离需要是m+i-1的倍数，且跳跃距离不能为0，问跳到每个点的方案数。

分析： 设状态为dp[i][j]，表示用i次跳跃到达j点的方案数，对于最后一次跳跃可以枚举跳跃长度是m+i-1的多少倍，不过这样显然会超时且超内存，由于跳跃倍数可以是1~∞，这样就有点像完全背包了，所以类比完全背包的递推优化也可以对这道题的递推进行优化：

这样就把三重循环优化到了两重循环，不过空间上也需要优化，因为650*200000是开不下的，空间优化可以用滚动数组，不过要注意对用完的值进行清空，这点有点类似之前的多校题：[dp]Two Permutations 2022杭电多校第3场

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
 
const int mod = 998244353;
int dp[2][200005];//用i步走到j的方案数 
int ans[200005];
 
signed main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 1; i*m <= n; i++){
		dp[1][i*m] = 1;
		ans[i*m]++;
	}
	for(int i = 2; (2*m+i-1)*i/2 <= n; i++){//这层循环最多700次 
		for(int j = m; j <= n; j++){
			//枚举最后一步是m+i-1的几倍，剩下的距离要用i-1步到达 
			if(j-(m+i-1) >= 0)//类似完全背包的优化 
				dp[i&1][j] = (dp[(i-1)&1][j-(m+i-1)]+dp[i&1][j-(m+i-1)])%mod;
			ans[j] = (ans[j]+dp[i&1][j])%mod; 
		}
		for(int j = 1; j <= n; j++)
			dp[(i-1)&1][j] = 0;
	}
	for(int i = 1; i <= n; i++)
		printf("%lld ", ans[i]);
    return 0;
}
//dp[i][j] = dp[i-1][j]+dp[i][j-v[i]]+w[i]