1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import sys
import math

wiersze = sys.stdin.read().strip().splitlines()
A, B, C = (wiersze[i].strip() for i in range(3))
n = len(A)
if n == 0:
    print(0)
    sys.exit(0)

ra = A[::-1]
rb = B[::-1]
rc = C[::-1]

sumy_cyfr = [(ord(ra[i]) - 48) + (ord(rb[i]) - 48) for i in range(n)]
wymagane_wejscie       = [-1] * n
wyjsciowe_przeniesienie = [-1] * n

for i in range(n):
    cel = ord(rc[i]) - 48
    for cin in (0, 1):
        if (sumy_cyfr[i] + cin) % 10 == cel:
            if wymagane_wejscie[i] == -1:
                wymagane_wejscie[i]        = cin
                wyjsciowe_przeniesienie[i] = (sumy_cyfr[i] + cin) // 10

LOG = max(1, math.ceil(math.log2(n + 1)))

poprawny          = [[bytearray(n) for _ in range(2)] for __ in range(LOG)]
przeniesienie_wyj = [[bytearray(n) for _ in range(2)] for __ in range(LOG)]
dobre             = [[[0] * n for _ in range(2)] for __ in range(LOG)]

for c in (0, 1):
    for i in range(n):
        if wymagane_wejscie[i] == c:
            poprawny[0][c][i]          = 1
            przeniesienie_wyj[0][c][i] = wyjsciowe_przeniesienie[i]
            dobre[0][c][i]             = 1 if wyjsciowe_przeniesienie[i] == 0 else 0

dlugosc = 1
for k in range(1, LOG):
    for c in (0, 1):
        for i in range(n):
            j = i + dlugosc
            if j >= n:
                continue
            if poprawny[k-1][c][i]:
                srodek = przeniesienie_wyj[k-1][c][i]
                if poprawny[k-1][srodek][j]:
                    poprawny[k][c][i]          = 1
                    przeniesienie_wyj[k][c][i] = przeniesienie_wyj[k-1][srodek][j]
                    dobre[k][c][i]             = dobre[k-1][c][i] + dobre[k-1][srodek][j]
    dlugosc <<= 1

wynik = 0
for poczatek in range(n):
    pozycja      = poczatek
    przeniesienie = 0
    for k in range(LOG - 1, -1, -1):
        if pozycja < n and poprawny[k][przeniesienie][pozycja]:
            wynik        += dobre[k][przeniesienie][pozycja]
            przeniesienie = przeniesienie_wyj[k][przeniesienie][pozycja]
            pozycja      += (1 << k)

print(wynik)