Задача 8. A+B ≡

Условие

Рассмотрим a, b и c — целые неотрицательные числа, записанные в десятичной системе счисления. Пусть они имеют одинаковую длину n, при этом запись может начинаться с нуля. Числа записаны одно под другим, цифры расположены в три строки и n столбцов. Рассмотрим пример такой записи:

  01211
  12099
  23300
  

Требуется переставить столбцы в этой записи таким образом, чтобы выполнялось равенство a + b = c. В полученной записи ведущие нули уже запрещены. Сколько существует различных способов это сделать?

Перестановки столбцов считаются различными, даже если полученные записи совпадают. Например, если в записи выше переставить два последних столбца, получится другая перестановка, хотя цифры в этих колонках совпадают.

Поскольку ответ может быть довольно большим, требуется посчитать для него остаток по модулю 10⁹ + 7.

Формат входных данных

Во входных данных записаны целые неотрицательные числа a, b и c по одному в строке. Каждое число состоит из n десятичных цифр и может начинаться с нуля.

Формат выходных данных

Выведите количество подходящих перестановок столбцов по модулю 10⁹ + 7.

Ограничения

2 ≤ n ≤ 2 ⋅ 10⁵

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснения к примерам

В первом примере подходят все перестановки столбцов.

Во втором примере единственная подходящая перестановка — 10 + 20 = 30. 01 + 02 = 03 не считается из-за наличия ведущих нулей.

В третьем примере возможны варианты 10121 + 21909 = 32030 и 12101 + 20919 = 33020, причём каждый из них может быть получен двумя разными перестановками.

Примеры тестов

123
123
246

6

01
02
03

1

01211
12099
23300

4

121
214
999

0

Разбор

Подзадача 1

Первая подзадача решается перебором n! перестановок.

Подзадача 2

Каждый столбец можно охарактеризовать тремя параметрами (обозначим цифры в нём за a_i, b_i, c_i):

1. Есть ли в нём цифра ноль (это влияет на то, может ли он быть первым).
2. Требуется ли ему перенос из столбца справа, в зависимости от того, верно (a_i + b_i) mod 10 = c_i или (a_i + b_i + 1) mod 10 = c_i. Если ни одно из этих равенств не выполнено, то ответ 0. Обозначим этот параметр needCarry_i ∈ {0,1}.
3. Создаёт ли этот столбец перенос через разряд. Это так, когда a_i + b_i + needCarry_i ≥ 10. Обозначим этот столбец makeCarry_i ∈ {0,1}.

Будем выбирать перестановку столбцов слева направо. Первым может идти столбец без нулей и не создающий переноса. Если после столбца i идёт столбец j, то needCarry_i = makeCarry_j. Для последнего столбца needCarry_i = 0. Получается граф, в котором нужно найти число гамильтоновых путей. Это можно сделать при помощи динамического программирования за O(2ⁿ n²), решив, таким образом, вторую подзадачу.

Подзадачи 3 и 4

В полученном графе есть четыре вида вершин в зависимости от значений needCarry_i и makeCarry_i. Обозначим эти виды следующим образом:

• Тип A: needCarry_i = 0, makeCarry_i = 0
• Тип B: needCarry_i = 1, makeCarry_i = 0
• Тип C: needCarry_i = 0, makeCarry_i = 1
• Тип D: needCarry_i = 1, makeCarry_i = 1

На рисунке показано, какие рёбра есть в графе, а также какие вершины могут быть начальными и конечными.

Посчитать гамильтоновы пути в таком графе можно динамикой за O(n⁴): d_x[A][B][C][D] — число путей, которые заканчиваются в вершине вида x и проходят через соответствующее число вершин каждого вида. Это решает подзадачу 3.

Чтобы решить подзадачу 4, нужно учесть, что нельзя начинать со столбца с нулём. Это влияет только на базу динамики: в d_A[1][0][0][0] и d_B[0][1][0][0] нужно записать количество соответствующих столбцов, в которых нет нулей.

Подзадачи 5 и 6

На любом пути в таком графе, который начинается в A или B, количество вершин вида B не более чем на один превосходит количество вершин вида C. Это позволяет сократить число состояний в динамике до O(n³), решив, таким образом, подзадачи 5 и 6.

Подзадача 7

Обозначим за A, B, C, D количество вершин каждого вида. Любой интересующий нас путь выглядит следующим образом:

_B_C_B_C_B_C… B_C_

При этом вершины A расположены в промежутках перед B, а также в последнем. Вершины D расположены в промежутках после B. Кроме того, если B ≠ C, то ответ 0.

Если B = C = 0 и D > 0, то ответ 0. Если B = C = 0 и D = 0, то ответ A!.

Если B = C > 0, то ответом будет произведение следующих чисел:

1. Количество способов расставить вершины B по местам: B!
2. Количество способов расставить вершины C по местам: B!
3. Количество способов расставить A вершин в B + 1 промежуток с учётом порядка: (A + B)!B!
4. Количество способов расставить D вершин в B промежутков с учётом порядка: (D + B − 1)!(B − 1)!

Ответ равен (A + B)!(D + B − 1)!B. Это решение за O(n) проходит подзадачу 7.

Подзадача 8

Осталось учесть, что среди вершин вида A и B может быть сколько-то вершин, с которых нельзя начинать (столбцы с нулями). Обозначим эти количества за A₀ и B₀.

Как и в прошлой подзадаче, если B = C = 0 и D > 0, то ответ 0. Если B = C = 0 и D = 0, то ответ (A − 1)! ⋅ (A − A₀).

Далее B = C > 0. Сначала отдельно посчитаем:

• ans_B — число путей, которые начинаются с вершины вида B. Это означает, что промежутков, в которые можно ставить вершины A, не B + 1, а B. Тогда ans_B = B! ⋅ B! ⋅ (A + B − 1)!(B − 1)! ⋅ (D + B − 1)!(B − 1)! = (A + B − 1)!(D + B − 1)!B²
• ans_A — число путей, которые начинаются с вершины вида A. ans_A = (A + B)!(D + B − 1)!B − ans_B

Ответ равен ans_A ⋅ A − A₀A + ans_B ⋅ B − B₀B.