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
94
95
96
97
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main() {
    std::string a_str, b_str, c_str;
    std::cin >> a_str >> b_str >> c_str;
    int n = a_str.size();
    std::vector<int> a(n), b(n), c(n);
    for (size_t i = 0; i < n; i++)
    {
        a[i] = a_str[i] - '0';
    }

    for (size_t i = 0; i < n; i++)
    {
        b[i] = b_str[i] - '0';
    }

    for (size_t i = 0; i < n; i++)
    {        
        c[i] = c_str[i] - '0';
    }

    std::reverse(a.begin(), a.end());
    std::reverse(b.begin(), b.end());
    std::reverse(c.begin(), c.end());

    std::vector<bool> carry_rec(n), carry_gen(n);
    std::vector<long long> pref_recs(n + 1);
    
    for (size_t i = 0; i < n; i++)
    {
        carry_rec[i] = (a[i] + b[i] + 1) % 10 == c[i] % 10;
        carry_gen[i] = (carry_rec[i] && a[i] + b[i] + 1 > 9) || ((a[i] + b[i]) % 10 == c[i] % 10 && a[i] + b[i] > 9);
    }
    
    for (size_t i = 0; i < n; i++)
    {
        pref_recs[i + 1] = pref_recs[i] + 1 - carry_rec[i];
    }
    

    auto seek = [&](int i) -> std::pair<bool, int> {
        bool carry = false;
        while (i < n) {
            if ((a[i] + b[i] + carry) % 10 != c[i]) {
                return {false, i + (1 - carry)};
            }
            if (a[i] + b[i] + carry > 9) {
                carry = true;
                i++;
            }
            else {
                return {true, i + 1};
            }
        }
        return {false, i};
    };

    auto calc = [&](int l, int r) -> long long {
        long long out = 0;
        for (size_t i = r; i <= l; i++)
        {
            if (!carry_gen[i])
                out += pref_recs[i + 1] - pref_recs[r];
        }
        return out;
    };

    // closed-closed intervals
    int r = 0;
    bool curr_success = false;
    long long out = 0;

    int i = 0;
    while (i < n) {
        auto [status, next_check] = seek(i);
        if (status) {
            if (!curr_success) r = i;
        }
        else {
            if (curr_success) {
                out += calc(i - 1, r);
            }
        }

        curr_success = status;
        i = next_check;
    }
    if (curr_success) {
        out += calc(n - 1, r);
    }

    std::cout << out << '\n';
}