Cuộc họp

Xem PDF
Tác giả:
cuom1999
Dạng bài
Điểm: 700 (p) Thời gian: 5.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trong phòng họp, có \(m\) chiếc ghế xếp ngang. Có tối đa \(n\) người sẽ tham dự cuộc họp. Mỗi người sẽ ngồi một ghế hoặc hai ghế kề nhau (một ghế cho đồ dùng cá nhân). Cho trước \(m, n\), hãy xác định xem nếu có đúng \(i \ (1 \leq i \leq n)\) người thứ \(1, 2, ..., i\) tham gia cuộc họp thì có bao nhiêu cách sắp ghế cho họ. Biết rằng người \(x\) luôn ngồi phía bên trái người \(y\) nếu \(1 \leq x < y \leq i\).

Hai cách xếp được gọi là khác nhau nếu có một người ngồi ở vị trí khác nhau trong 2 cách đó.

Input

  • Gồm hai số \(m, n \ (0 < m \leq 10^9, 0 < n < 2^{15})\) tương ứng là số ghế và số người tối đa sẽ tham gia.

Output

  • In ra \(n\) số, số thứ \(i\) là số cách xếp ghế nếu có \(i\) người tham gia. Vì đáp số rất lớn nên các bạn hãy ra số dư của nó khi chia cho \(998244353\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(n, m \leq 1000\)
  • Subtask \(2\) (\(30\%\) số điểm): \(n \leq 1000\)
  • Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm

Test 1

Input 
3 3
Output 
5 5 1
Note
  • Nếu có một người tham gia, các cách xếp là \([1, 0, 0], [0, 1, 0], [0, 0, 1], [1, 1, 0], [0, 1, 1]\)
  • Nếu có hai người tham gia, các cách xếp là \([1, 2, 0], [0, 1, 2], [1, 0, 2], [1, 2, 2], [1, 1, 2]\)
    Trong đó \(0\) nghĩa là ghế đó không có người ngồi.

Test 2

Input 
1 1
Output 
1

Test 3

Input 
5 10
Output 
9 25 25 9 1 0 0 0 0 0

Bình luận