Codeforces Round 572 (Div. 1) |
---|
Закончено |
На Moscow Workshops ICPC команды получают воздушные шарики за каждую задачу, которую они решили первыми. Команда MSU Red Panda получила так много шариков, что они не знали, что с ними делать. Тогда они придумали о них задачу.
Есть несколько шариков, всего не более $$$10^6$$$, каждый покрашен в один из $$$k$$$ цветов. Мы можем делать следующую операцию: выбрать $$$k-1$$$ шариков $$$k-1$$$ различных цветов, и перекрасить их все в оставшийся цвет. Мы можем выполнять данную операцию любое конечное число раз (в частности, мы можем выполнить очередную операцию только если существует по крайней мере $$$k-1$$$ различных цветов среди шариков в данный момент).
Сколько различных конфигураций шариков мы можем получить? Играет роль только количество шариков каждого цвета, конфигурации, отличающиеся только порядком шариков, считаются одинаковыми. Так как это число может быть очень большим, выведите его по модулю $$$998244353$$$.
Первая строка содержит одно целое число $$$k$$$ ($$$2 \le k \le 10^5$$$) —количество цветов.
Вторая строка содержит $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$0 \le a_i$$$) —начальную конфигурацию шариков. $$$a_i$$$ равно количеству шариков цвета $$$i$$$. Общее число шариков не превосходит $$$10^6$$$. Другими словами,
$$$a_1 + a_2 + a_3 + \ldots + a_k \le 10^6$$$.
Выведите число возможных конфигураций по модулю $$$998244353$$$.
3 0 1 2
3
4 1 1 1 1
5
5 0 0 1 2 3
1
3 2 2 8
31
В первом примерe существуют $$$3$$$ конфигурации которые мы можем получить: $$$[0, 1, 2]$$$, $$$[2, 0, 1]$$$, $$$[1, 2, 0]$$$.
В втором примере мы можем применить операцию не более одного раза, и достижимыми являются : $$$[1, 1, 1, 1]$$$, $$$[0, 0, 0, 4]$$$, $$$[0, 0, 4, 0]$$$, $$$[0, 4, 0, 0]$$$, $$$[4, 0, 0, 0]$$$.
В третьем примере мы не можем применить ни одной операции, поэтому единственная достижимая конфигурация - начальная.
Название |
---|