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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstdio>
#include <cstring>

#ifdef LOCAL
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

char strnumbers[3][1000001];
int numbers[3][1000001];

int main() {
    scanf("%s", strnumbers[0]);
    scanf("%s", strnumbers[1]);
    scanf("%s", strnumbers[2]);

    unsigned long n = strlen(strnumbers[0]);

    dbg("Numbers have %lu digits\n", n);

    for (int i = 0; i < n; ++i) {
        for (int si = 0; si < 3; ++si) {
            numbers[si][i] = strnumbers[si][n-(i+1)] - '0';
        }
    }

    for (int si = 0; si < 3; ++si) {
        for (int i = 0; i < n; ++i) {
            dbg("%d ", numbers[si][i]);
        }
        dbg("\n");
    }



    long long totalres = 0LL;
    long long correct[2][2][2] = {{{0LL, 0LL},{0LL, 0LL}},{{0LL, 0LL},{0LL, 0LL}}};
    // correct[PHASE][X][Y] = number of correct combinations that require X carryover from previous value and give Y carryover to the next

    int curidx = 0;
    int previdx = 1;

    for (int i = 0; i < n; ++i) {
        int res = numbers[0][i] + numbers[1][i];

        // if not receiving carryover from previous digit
        int digit_if_0 = res % 10;
        bool digit_eq_if_0 = digit_if_0 == numbers[2][i];
        bool carryover_if_0 = res >= 10;

        // if receiving carryover from previous digit
        int digit_if_1 = (res+1) % 10;
        bool digit_eq_if_1 = digit_if_1 == numbers[2][i];
        bool carryover_if_1 = (res+1) >= 10;

        correct[curidx][0][0] = 0LL;
        correct[curidx][0][1] = 0LL;
        correct[curidx][1][0] = 0LL;
        correct[curidx][1][1] = 0LL;

        dbg("%d + %d = %2d\n", numbers[0][i], numbers[1][i], res);
        dbg("expected: %d\n", numbers[2][i]);

        if (digit_eq_if_0) {
            if (!carryover_if_0) {
                // simple equals, e.g. 3 + 4 = 7
                correct[curidx][0][0] += correct[previdx][0][0] + correct[previdx][1][0] + 1;
                dbg("Creating 0-0...\n");
                dbg("  We can extend %lld previous 0-0 numbers.\n", correct[previdx][0][0]);
                dbg("  We can extend %lld previous 1-0 numbers.\n", correct[previdx][1][0]);
                dbg("  We can start one new number.\n");
                dbg("Total creatable 0-0 numbers: %lld", correct[curidx][0][0]);
            } else {
                // teen equals, e.g. 8 + 9 = 7 (+10)
                correct[curidx][0][1] += correct[previdx][0][0] + correct[previdx][1][0] + 1;
                dbg("Creating 0-1...\n");
                dbg("  We can extend %lld previous 0-0 numbers.\n", correct[previdx][0][0]);
                dbg("  We can extend %lld previous 1-0 numbers.\n", correct[previdx][1][0]);
                dbg("  We can start one new number.\n");
                dbg("Total creatable 0-1 numbers: %lld", correct[curidx][0][1]);
            }
        }
        // else: nonequality, breaks all sums.

        if (digit_eq_if_1) {
            if (!carryover_if_1) {
                // simple equals if carryover present, e.g. 3 + 4 (+1) = 8
                correct[curidx][1][0] += correct[previdx][0][1] + correct[previdx][1][1];
                dbg("Creating 1-0...\n");
                dbg("  We can extend %lld previous 0-1 numbers.\n", correct[previdx][0][1]);
                dbg("  We can extend %lld previous 1-1 numbers.\n", correct[previdx][1][1]);
                dbg("Total creatable 1-0 numbers: %lld", correct[curidx][1][0]);
            } else {
                // teen equals if carryover present, e.g. 7 + 8 (+1) = 6 (+10)
                correct[curidx][1][1] += correct[previdx][0][1] + correct[previdx][1][1];
                dbg("Creating 1-1...\n");
                dbg("  We can extend %lld previous 0-1 numbers.\n", correct[previdx][0][1]);
                dbg("  We can extend %lld previous 1-1 numbers.\n", correct[previdx][1][1]);
                dbg("Total creatable 1-1 numbers: %lld", correct[curidx][1][1]);
            }
        }
        // else: nonequality, breaks all sums.

        totalres += correct[curidx][0][0] + correct[curidx][1][0];
        previdx = 1 - previdx;
        curidx = 1 - curidx;
    }

    printf("%lld\n", totalres);
    return 0;
}