| Codeforces Round 250 (Div. 1) |
|---|
| Закончено |
Наш ребенок обожает информатику, особенно двоичные деревья.
Рассмотрим последовательность из n различных целых чисел: c1, c2, ..., cn. Ребенок называет двоичное корневое дерево со взвешенными вершинами хорошим тогда и только тогда, когда для каждой вершины v, вес v — это элемент множества {c1, c2, ..., cn}. Также наш ребенок считает, что вес дерева со взвешенными вершинами равняется сумме весов всех вершин.
Задано число m, сможете ли вы для всех s (1 ≤ s ≤ m) посчитать количество хороших двоичных корневых деревьев со взвешенными вершинами с весом s? Для более глубокого понимания того, какие деревья считаются различными, пожалуйста, посмотрите примеры тестовых данных.
Выведите ответ по модулю 998244353 (7 × 17 × 223 + 1, простое число).
В первой строке записано два целых числа n, m (1 ≤ n ≤ 105; 1 ≤ m ≤ 105). Во второй строке записано n попарно различных целых чисел через пробел c1, c2, ..., cn (1 ≤ ci ≤ 105).
Выведите m строк, каждая строка должна содержать единственное целое число. В i-й строке должно быть записано количество хороших двоичных корневых деревьев со взвешенными вершинами с весом i. Выведите ответ по модулю 998244353 (7 × 17 × 223 + 1, простое число).
2 3
1 2
1
3
9
3 10
9 4 3
0
0
1
1
0
2
4
2
6
15
5 10
13 10 6 4 15
0
0
0
1
0
1
0
2
0
5
В первом примере существует 9 хороших двоичных корневых деревьев со взвешенными вершинами, чей вес равняется ровно 3:
