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
#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

int main() {

    string A, B, C;
    getline(cin, A);
    getline(cin, B);
    getline(cin, C);

    int n = A.size();

    long long current_dp0 = 0;
    long long current_dp1 = 0;

    long long total_valid_intervals = 0;

    for (int i = n - 1; i >= 0; --i) {
        int a = A[i] - '0';
        int b = B[i] - '0';
        int c = C[i] - '0';

        long long next_dp0 = 0;
        long long next_dp1 = 0;

        int sum_val = a + b;

        if (sum_val == c) {
            next_dp0++;
        }
        if (sum_val == c) {
            next_dp0 += current_dp0;
        }
        if (sum_val + 1 == c) {
            next_dp0 += current_dp1;
        }

        if (sum_val == 10 + c) {
            next_dp1++;
        }
      
        if (sum_val == 10 + c) {
            next_dp1 += current_dp0;
        }
        if (sum_val + 1 == 10 + c) {
            next_dp1 += current_dp1;
        }

        current_dp0 = next_dp0;
        current_dp1 = next_dp1;

        total_valid_intervals += current_dp0;
    }

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