Спрятанные блины
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Стек, очередь, связные списки
- Деревья и графы
- Математика
Пекут n блинов радиусов 1, 2, …, n (каждый радиус ровно один раз) в некотором порядке. Каждый новый блин кладут на верх стопки, центры совпадают. Блин виден сверху, пока на него не положили блин большего радиуса; блин, который хоть раз накрыли бо́льшим, больше не виден.
Дан список visible длины n: visible[i] — сколько блинов видно сверху сразу после того, как в стопке оказались первые i + 1 блинов. Верните, сколько из n! порядков выпекания дают ровно такой список, по модулю простого 1000000007. Если такой порядок невозможен (например, видимых стало больше, чем на один, по сравнению с предыдущим шагом), верните 0.
Гарантируется 1 ≤ visible[i] ≤ i + 1; n до нескольких тысяч, поэтому перебор порядков не подходит.
Пример: [1, 2, 2, 1] → 1 (подходит только порядок 3, 1, 2, 4).
Источник: Coding Competitions Archive, codejam/2021/round_2/hidden_pancakes · © Google LLC · Apache-2.0 · условие переведено и дополнено