Олимпиадный тренинг

Задача . D. Мастер СНМ

Задача

Темы: дп Комбинаторика математика снм *2500

Вам дано целое число $n$ и массив $a$ длины $n-1$, элементы которого либо $0$, либо $1$.

Определим стоимость перестановки $^\dagger$ $p$ длины $m-1$ ($m \leq n$) следующим образом.

Пусть $G$ - граф из $m$ вершин с номерами от $1$ до $m$, не содержащий ребер. Для каждого $i$ от $1$ до $m-1$ выполните следующие операции:

определим $u$ и $v$ как (различные) вершины с только входящими ребрами$^{\dagger\dagger}$ в компонентах слабой связности $^\ddagger$, содержащих вершины $p_i$ и $p_i+1$ соответственно
в графе $G$, добавим направленное ребро из вершины $v$ в $u$, если $a_{p_i}=0$, иначе добавим направленное ребро из вершины $u$ в $v$ (если $a_{p_i}=1$).

Заметим, что после каждого шага можно показать, что каждая компонента слабой связности $G$ имеет ровно одну вершину с только входящими рёбрами.

Тогда, значение $p$ — это количество входящих ребер $G$ в вершину $1$.

Для каждого $k$ от $1$ до $n-1$ найдите сумму стоимостей всех $k!$ перестановок длины $k$. Поскольку эта величина может быть большой, от вас требуется вычислить ее только по модулю $998\,244\,353$.

$\text{[math]}$ Операции при $n=3$, $a=[0,1]$ и $p=[1,2]$

$^\dagger$ Перестановка длины $n$ - это массив, состоящий из $n$ различных целых чисел от $1$ до $n$ в произвольном порядке. Например, $[2,3,1,5,4]$ - перестановка, но $[1,2,2]$ - не перестановка ($2$ встречается в массиве дважды), и $[1,3,4]$ - тоже не перестановка ($n=3$, но в массиве есть $4$).

$^\ddagger$ Компоненты слабой связности направленного графа — это то же самое, что и компоненты неориентированной версии графа. Формально, для направленного графа $G$ определите граф $H$, где для всех ребер $a \to b$ в $G$ добавляется неориентированное ребро $a \leftrightarrow b$ в $H$. Тогда компоненты слабой связности $G$ являются компонентами $H$.

$^{\dagger\dagger}$ Заметим, что вершина, не имеющая ребер, считается имеющей только входящие ребра.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $t$ ($1\le t\le 10^4$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно число $n$ ($2\le n\le 5 \cdot 10^5$).

Вторая строка содержит $n-1$ чисел $a_1, a_2, \ldots, a_{n-1}$ ($a_i$ равно $0$ или $1$).

Гарантируется, что сумма значений $n$ по всем наборам входных данных не превосходит $5 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных выведите $n-1$ целых чисел в строке. $i$-е число является ответом для $k=i$, по модулю $998\,244\,353$.

Примечание

Рассмотрим первый набор входных данных.

Когда $k=1$, существует только $1$ перестановка $p$.

Когда $p=[1]$, мы добавим одно ребро из вершины $2$ в $1$. Вершина $1$ будет иметь $1$ входящее ребро. Поэтому значение $[1]$ равно $1$.

Поэтому, когда $k=1$, ответ равен $1$.

Когда $k=2$, существует $2$ перестановки $p$.

Когда $p=[1,2]$, мы добавим ребро из вершины $2$ в $1$ и ребро из $3$ в $1$. Вершина $1$ будет иметь $2$ входящих ребер. Таким образом, значение $[1,2]$ равно $2$.
Когда $p=[2,1]$, мы добавим ребро из вершины $3$ в $2$ и ребро из $2$ в $1$. Вершина $1$ будет иметь входящее ребро $1$. Таким образом, значение $[2,1]$ равно $1$.

Поэтому, когда $k=2$, ответ будет $2+1=3$.

Примеры

№	Входные данные	Выходные данные
1	2 3 0 0 9 0 1 0 0 0 1 0 0	1 3 1 2 7 31 167 1002 7314 60612

time 2000 ms
memory 1024 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет