Mex Permutations#231

Mex Permutations (Editorial)

Спершу з'ясуємо, коли масив $F$ узагалі коректний. Величина $mex$ від дедалі більшої множини не може спадати, тому $F$ мусить бути неспадним. Крім того, після всіх $n$ елементів множина — це ${0, 1, \dots, n - 1}$ \{0, 1, \ldots, n-1\}, отже $F_{n} = n$ F_n = n. Якщо щось із цього порушено, відповідь нульова.

Тепер розглянемо, що відбувається на кожному кроці. Нехай $last = F_{i - 1}$ \mathit{last} = F_{i-1} — поточне значення $mex$ перед позицією $i$ .

Крок без зростання ( $F_{i} = last$ F_i = \mathit{last}). Значення $mex$ не змінилось, отже на позицію $i$ поставили щось, що його не «розблокувало», — тобто будь-яке ще не використане число, крім самого $last$ . Ми поки не фіксуємо, яке саме: така позиція залишається «вільним слотом», і чим її заповнити, вирішиться пізніше.

Крок зі зростанням ( $F_{i} > last$ F_i > \mathit{last}). Щоб $mex$ зрушив з місця, на позицію $i$ мусить потрапити рівно число $last$ — тут вибору немає. А щоб він стрибнув аж до $F_{i}$ F_i, усі числа

last + 1, last + 2, \dots, F_{i} - 1

\mathit{last}+1,\; \mathit{last}+2,\; \ldots,\; F_i - 1

мають уже бути присутніми серед перших $i$ елементів. Їх рівно $nums = F_{i} - last - 1$ \mathit{nums} = F_i - \mathit{last} - 1 штук.

Скільки є місць, куди їх можна було покласти? Серед перших $i$ позицій уже стоять $i$ різних чисел, серед яких обов'язково всі $0, 1, \dots, last - 1$ 0, 1, \ldots, \mathit{last}-1 (бо $mex$ дорівнює $last$ ). Отже, позицій, зайнятих числами, більшими за $last$ , рівно

spots = i - last,

\mathit{spots} = i - \mathit{last},

і саме це і є ті «вільні слоти», які ми досі не заповнювали.

Тепер вибір: які саме $nums$ із $spots$ слотів отримають потрібні числа і в якому порядку. Це кількість розміщень

A (spots, nums) = \frac{spots !}{( spots - nums )!} .

A(\mathit{spots}, \mathit{nums}) = \frac{\mathit{spots}!}{(\mathit{spots} - \mathit{nums})!}.

Відповідь — добуток цих величин по всіх кроках зі зростанням (кроки без зростання множників не дають, бо їхній вибір відкладається). Оскільки $F_{n} = n$ F_n = n, наприкінці всі слоти виявляються заповненими, тож жодної невизначеності не лишається.

Факторіали та обернені до них за модулем $998244353$ рахуємо заздалегідь, тому весь розв'язок — це один прохід за $O (n)$ .