Эта задача отличается от предыдущей исключительно отсутствием ограничения на равную длину всех чисел \(a_1, a_2, \dots, a_n\).
Команда ЛКШ-ат собралась совершить путешествие на подводной лодке. Цель их плавания — древний клад на затонувшем судне, лежащем на дне Великого Рыбинского моря. К сожалению, ребята не знают координаты судна, и поэтому обратились за помощью к потомственному магу Мишане. Он согласился помочь команде, но только если они решат его задачку.
Определим функцию, чередующую цифры двух чисел, \(f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q)\), где \(a_1 \dots a_p\) и \(b_1 \dots b_q\) — цифры двух чисел в десятичной системе счисления, записанные без ведущих нулей.
Иными словами, функция \(f(x, y)\) перемешивает цифры чисел \(x\) и \(y\) выписывая их по очереди от младщих цифр к старшим, начиная с числа \(y\). Результат функции тоже строится справа налево (то есть от младших цифр к старшим). Если цифры одного из аргументов закончились, то выписываются оставшиеся цифры другого аргумента. Ознакомьтесь с примерами и формальным определением функции.
Например: \(\)f(1111, 2222) = 12121212\(\) \(\)f(7777, 888) = 7787878\(\) \(\)f(33, 44444) = 4443434\(\) \(\)f(555, 6) = 5556\(\) \(\)f(111, 2222) = 2121212\(\)
Формально:
- если \(p \ge q\), то \(f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q\);
- если \(p < q\), то \(f(a_1 \dots a_p, b_1 \dots b_q) = b_1 b_2 \dots b_{q - p} a_1 b_{q - p + 1} a_2 \dots a_{p - 1} b_{q - 1} a_p b_q\).
Мишаня дал вам массив из \(n\) целых чисел \(a_i\), помогите ребятам посчитать \(\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)\) по модулю \(998\,244\,353\).