/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 2500 点
問題文
正整数 N,M が与えられます．ここで，N<M です．
長さ N の非負整数列 a=(a_1,a_2,\cdots,a_N) であって，以下の条件を満たすものをよい数列と呼ぶことにします．
- 0 \leq a_1 \leq a_2 \leq \cdots \leq a_N \leq M
よい数列 a について，(a_1-1,a_2-2,\cdots,a_N-N) を昇順にソートして得られる数列を f(a) と表すことにします．
各 k=1,2,\cdots,N について，次の問題を解いてください．
- あり得るすべてのよい数列 a に対して f(a) の k 番目の要素を求めたとする． これらの値の総和を 998244353 で割ったあまりを求めよ．
※ 負の数を割ったあまりも 0 以上 998244353 未満の範囲で求めてください．
制約
- 1 \leq N < M \leq 10^6
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられる．
N M
出力
N 行出力せよ． i 行目には k=i に対する答えを出力せよ．
入力例 1
2 3
出力例 1
998244349 4
あり得る a とそれに対応する f(a) は以下の通りです．
- a=(0,0): f(a)=(-2,-1)
- a=(0,1): f(a)=(-1,-1)
- a=(0,2): f(a)=(-1,0)
- a=(0,3): f(a)=(-1,1)
- a=(1,1): f(a)=(-1,0)
- a=(1,2): f(a)=(0,0)
- a=(1,3): f(a)=(0,1)
- a=(2,2): f(a)=(0,1)
- a=(2,3): f(a)=(1,1)
- a=(3,3): f(a)=(1,2)
よって，f(a) の 1 番目の要素の総和は -4 になり，f(a) の 2 番目の要素の総和は 4 になります．
入力例 2
3 4
出力例 2
998244329 0 24
入力例 3
4 6
出力例 3
998244233 35 175 330
入力例 4
10 1000000
出力例 4
297189103 747015740 88545731 123651717 920498165 977169022 775771117 810877103 152407094 602233731
Score : 2500 points
Problem Statement
You are given positive integers N and M. Here, N<M.
A sequence of N non-negative integers a=(a_1,a_2,\cdots,a_N) is said to be a good sequence when it satisfies the following condition:
- 0 \leq a_1 \leq a_2 \leq \cdots \leq a_N \leq M.
For a good sequence a, let f(a) be the sequence resulting from sorting (a_1-1,a_2-2,\cdots,a_N-N) in ascending order.
For each k=1,2,\cdots,N, solve the following problem.
- Assume that we have found the k-th element of f(a) for every possible good sequence a. Find the sum, modulo 998244353, of these values.
※ The answer should be between 0 and 998244352 even if the sum is negative.
Constraints
- 1 \leq N < M \leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print N lines. The i-th line should contain the answer for k=i.
Sample Input 1
2 3
Sample Output 1
998244349 4
Here are all possible a and the corresponding f(a).
- a=(0,0): f(a)=(-2,-1)
- a=(0,1): f(a)=(-1,-1)
- a=(0,2): f(a)=(-1,0)
- a=(0,3): f(a)=(-1,1)
- a=(1,1): f(a)=(-1,0)
- a=(1,2): f(a)=(0,0)
- a=(1,3): f(a)=(0,1)
- a=(2,2): f(a)=(0,1)
- a=(2,3): f(a)=(1,1)
- a=(3,3): f(a)=(1,2)
Thus, the sum of the first elements is -4, and the sum of the second elements is 4.
Sample Input 2
3 4
Sample Output 2
998244329 0 24
Sample Input 3
4 6
Sample Output 3
998244233 35 175 330
Sample Input 4
10 1000000
Sample Output 4
297189103 747015740 88545731 123651717 920498165 977169022 775771117 810877103 152407094 602233731