Grakn Forces 2020 |
---|
Закончено |
В сети компании есть $$$n$$$ компьютеров. Они пронумерованы от $$$1$$$ до $$$n$$$.
Для каждой пары компьютеров $$$1 \leq i < j \leq n$$$ вы знаете значение $$$a_{i,j}$$$: сложность отправки сообщения между компьютерами $$$i$$$ и $$$j$$$. Значения $$$a_{i,j}$$$ для $$$i<j$$$ различны.
Вы хотите разделить компьютеры на $$$k$$$ множеств $$$A_1, A_2, \ldots, A_k$$$, чтобы следующие условия выполнялись:
Для каждого $$$1 \leq k \leq n$$$ найдите число способов разделить компьютеры на $$$k$$$ групп так, чтобы все упомянутые условия соблюдались. Эти значения могут быть большими, так что вам нужно найти их по модулю $$$998\,244\,353$$$.
В первой строке записано одно целое число $$$n$$$ ($$$1 \leq n \leq 1500$$$): количество компьютеров.
В $$$i$$$-й из следующих $$$n$$$ строк записаны $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$0 \leq a_{i,j} \leq \frac{n (n-1)}{2}$$$).
Гарантируется, что:
Выведите $$$n$$$ целых чисел: $$$k$$$-е из них должно быть равно числу способов разбить компьютеры на $$$k$$$ групп, соблюдая все описанные условия, по модулю $$$998\,244\,353$$$.
4 0 3 4 6 3 0 2 1 4 2 0 5 6 1 5 0
1 0 1 1
7 0 1 18 15 19 12 21 1 0 16 13 17 20 14 18 16 0 2 7 10 9 15 13 2 0 6 8 11 19 17 7 6 0 4 5 12 20 10 8 4 0 3 21 14 9 11 5 3 0
1 1 2 3 4 3 1
Ниже приведены все возможные разбиения компьютеров на $$$4$$$ группы для второго примера:
Название |
---|