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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <string>
#include <array>
using namespace std;

struct State {
    int to0, to1;

    bool operator==(const State& other) const {
        return to0 == other.to0 && to1 == other.to1;
    }
};

int id(const State& s) {
    return (s.to0 + 1) * 3 + (s.to1 + 1);
}

State fromId(int x) {
    return { x / 3 - 1, x % 3 - 1 };
}

State compose(const State& left, const State& right) {
    State res;

    auto apply = [&](int in) -> int {
        int mid = (in == 0 ? right.to0 : right.to1);
        if (mid == -1) return -1;
        return (mid == 0 ? left.to0 : left.to1);
        };

    res.to0 = apply(0);
    res.to1 = apply(1);
    return res;
}

State oneColumn(char a, char b, char c) {
    int x = a - '0';
    int y = b - '0';
    int z = c - '0';

    State s;

    auto calc = [&](int carry) -> int {
        int sum = x + y + carry;
        if (sum % 10 != z) return -1;
        return sum / 10;
        };

    s.to0 = calc(0);
    s.to1 = calc(1);
    return s;
}

int main() {
    string nap1, nap2, nap3;
    cin >> nap1 >> nap2 >> nap3;

    int n = nap1.size();
    if ((int)nap2.size() != n || (int)nap3.size() != n) {
        cout << 0;
        return 0;
    }

    long long res = 0;

    array<long long, 9> cnt{}, nextCnt{};

    for (int i = 0; i < n; i++) {
        State col = oneColumn(nap1[i], nap2[i], nap3[i]);
        int colId = id(col);

        nextCnt.fill(0);
        nextCnt[colId]++;
        for (int st = 0; st < 9; st++) {
            if (cnt[st] == 0) continue;
            State prev = fromId(st);
            State now = compose(prev, col);
            nextCnt[id(now)] += cnt[st];
        }
        for (int st = 0; st < 9; st++) {
            if (nextCnt[st] == 0) continue;
            State s = fromId(st);
            if (s.to0 == 0) {
                res += nextCnt[st];
            }
        }

        cnt = nextCnt;
    }

    cout << res;
    return 0;
}