Codeforces Round 831 (Div. 1 + Div. 2) |
---|
Закончено |
Паку Чанаку дан массив $$$a$$$ из $$$n$$$ целых чисел. Для каждого $$$i$$$ ($$$1 \leq i \leq n$$$) Пак Чанак пишет на доске одноэлементное множество $$$\{a_i\}$$$.
После этого за одну операцию Пак Чанак может сделать следующее:
Выполнив ноль или более операций, Пак Чанак построит мультимножество $$$M$$$, содержащее размеры всех множеств, написанных на доске. Другими словами, каждый элемент в $$$M$$$ соответствует размеру некоторого множества после операций.
Сколько различных$$$^\dagger$$$ мультимножеств $$$M$$$ может быть получено таким процессом? Так как ответ может быть большим, выведите его по модулю $$$998\,244\,353$$$.
$$$^\dagger$$$ Мультимножества $$$B$$$ и $$$C$$$ различны тогда и только тогда, когда существует значение $$$k$$$ такое, что количество элементов со значением $$$k$$$ в $$$B$$$ отличается от количества элементов со значением $$$k$$$ в $$$C$$$.
Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 2000$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).
Выведите количество различных мультимножеств $$$M$$$ по модулю $$$998\,244\,353$$$.
6 1 1 2 1 4 3
7
7 3 5 4 3 7 4 5
11
В первом примере возможные мультимножества $$$M$$$ таковы: $$$\{1,1,1,1,1,1\}$$$, $$$\{1,1,1,1,2\}$$$, $$$\{1,1,1,3\}$$$, $$$\{1,1,2,2\}$$$, $$$\{1,1,4\}$$$, $$$\{1,2,3\}$$$ и $$$\{2,2,2\}$$$.
В качестве примера рассмотрим возможную последовательность операций.
Название |
---|