Пряме порівняння всіх пар дало б \mathcal{O}((r-l)^2) операцій, що при r \le 10^6 занадто повільно. Але помітьмо: число впливає на відповідь лише через дві свої характеристики — першу й останню цифру.
Перша цифра може бути від до , остання — від до , тобто всього можливих типів. Тому згрупуємо числа за типом.
Одним проходом по всіх від до порахуємо \mathrm{cnt}[f][d] — скільки чисел мають першу цифру і останню . Останню цифру дає x \bmod 10, першу — послідовне ділення на , доки число не стане однозначним.
Тепер умова задачі мовою типів: якщо має тип , то мусить мати тип . Справді, перша цифра дорівнює і має збігатися з останньою цифрою ; остання цифра дорівнює і має збігатися з першою цифрою .
Отже, кожен тип дає \mathrm{cnt}[i][j] \cdot \mathrm{cnt}[j][i] пар, і відповідь — сума цього добутку по всіх від до та від до .
Пари та вважаються різними, а a = b дозволено — добуток лічильників враховує обидва випадки саме так, як треба, тому жодних поправок робити не потрібно.
Складність — \mathcal{O}(r - l + 100). Умова окремо попереджає: відповідь не вміщається у 32-бітний тип, тому обов'язково беріть 64-бітний.