Впорядковані цифри#38

Впорядковані цифри (Editorial)

Будуватимемо число зліва направо, і на кожному кроці нам важлива лише остання поставлена цифра — звідси природна динаміка.

Нехай — кількість способів заповнити перші цифр так, щоб -та цифра дорівнювала і всі умови a_1, \ldots, a_{i-1} виконувались.

База: перша цифра не може бути нулем (число має рівно n+1 цифру), тому \mathrm{dp}[1][d] = 1 для від до і \mathrm{dp}[1][0] = 0.

Перехід із позиції на i+1 визначається значенням a_i:

  • якщо a_i = 1, то b_{i+1} > b_i, тому \mathrm{dp}[i+1][d] = \sum_{d' < d} \mathrm{dp}[i][d'];

  • якщо a_i = 0, то b_{i+1} < b_i, тому \mathrm{dp}[i+1][d] = \sum_{d' > d} \mathrm{dp}[i][d'].

Відповідь — сума \mathrm{dp}[n+1][d] по всіх .

Наївно кожен перехід коштує \mathcal{O}(10^2), що при n \le 10^5 уже нормально (10^7 операцій), але ще краще — рахувати префіксні (відповідно суфіксні) суми по , і тоді перехід стає .

Не забувайте брати остачу за модулем 10^9 + 7 після кожного додавання.

Перевіримо на прикладі з умови: n = 1, a_1 = 0. Тоді відповідь — кількість пар b_1 > b_2 з b_1 \ge 1, тобто 1 + 2 + \ldots + 9 = 45.