- Описание
- Отправленные решения
430. Парные коды
Кодом товара называется некоторое целое неотрицательное число без ведущих нулей. Товары называются парными, если в их записи есть хотя бы одна одинаковая цифра. Например, товары с номерами $103$ и $20$ являются парными, а товары $123$ и $4567$ не являются парными.
Всего в базе магазина $n$ товаров с номерами $a_1, a_2, \ldots, a_n$. Вам интересно, сколько существует пар парных товаров — иначе говоря, таких пар $i < j$, что $a_i$ и $a_j$ содержат хотя бы одну одинаковую цифру в десятичной записи.
Формат ввода
Первая строка входного файла содержит число $N$($1\le N\le 500\ 000$) — количество товаров в базе.
Вторая строка содержит $n$ целых неотрицательных чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), разделённых пробелами, — номера товаров.
Формат вывода
Выведите единственное число — ответ на задачу.
Примечание
Первый тест соответствует товарам из условия. Можно заметить, что любая пара, составленная из товаров $103, 20, 123$, будет иметь общую цифру. Товар $4567$ не имеет общих цифр с оставшимися. Таким образом, ответ равен $3$.
Ограничения
Ограничение времени
3 с
Ограничение памяти
256 МБ
Пример 1
4
103 123 20 4567
3