Великі числа#404

Великі числа (Розбір)

Який порядок дає максимум. Класичний результат: щоб конкатенація набору чисел була найбільшою, треба відсортувати їх компаратором

u \prec v \iff u\,\|\,v \;>\; v\,\|\,u,

де — склеювання десяткових записів. Рівносильне й зручніше формулювання: порівнюємо нескінченні повторення та vvv\ldots лексикографічно. Наприклад, 9 \prec 89, бо 999\ldots > 898\ldots

Виписати сам порядок неможливо — чисел до 10^{17}. Але кожен запит — це «яка цифра стоїть на позиції », тож достатньо вміти для довільного швидко сказати, скільки цифр стоїть перед .

Скільки чисел випереджають . Розіб'ємо за довжиною запису. Зафіксуємо довжину і запитаємо: які з рівно цифрами йдуть перед ? З опису через нескінченні повторення випливає простий критерій. Нехай P_L(x) — перші цифр рядка , прочитані як число. Тоді

y \prec x \iff y \ge P_L(x),

причому поріг збільшуємо на одиницю, якщо саме P_L(x) ще не випереджає (це трапляється, коли не кратне довжині і «обрізане» повторення програє). Отже всередині кожного класу довжини множина випереджальних чисел — це просто суфікс числового відрізка, і його розмір рахується за :

\mathrm{cnt}_L = \max\bigl(0,\ \min(b,\,10^{L}-1) + 1 - \mathrm{clamp}(P_L(x),\,a,\,b+1)\bigr).

Сумуючи \mathrm{cnt}_L отримуємо ранг , а сумуючи L \cdot \mathrm{cnt}_L — позицію першої цифри у відповіді. Порогів усього \mathcal{O}(\log b).

Однакові числа за компаратором (як і ) утворюють «нічию»; будь-яке впорядкування таких дає той самий рядок, тож достатньо зафіксувати довільне правило (скажімо, більше число раніше) і не хвилюватися.

Відповідь на запит. Позиція першої цифри монотонно спадає зі зростанням числа в межах одного класу довжини (більші числа стоять раніше). Тому в кожному класі двійковим пошуком знаходимо число з найбільшою стартовою позицією, що не перевищує ; серед класів беремо кандидата з найбільшим рангом — це і є число, всередину якого потрапляє позиція . Далі лишається відняти стартову позицію й вивести відповідну цифру.

Дрібниця, що прискорює. Пороги P_L(x) для різних — вкладені префікси одного нескінченного рядка, тому межу для довжини L-1 отримуємо з межі для звичайним діленням на . Це дозволяє не запускати повний двійковий пошук у кожному класі окремо.

Обережно з переповненням. Порівняння і через числа дає до цифр — потрібен __int128 (або порівняння рядків).

Складність — \mathcal{O}\bigl(q \log^2 b\bigr) операцій, пам'ять \mathcal{O}(\log b).