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
#include <iostream>
using namespace std;
const long long MAXN = 1000005;
long long DP[MAXN][10];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string A, B, C;
    cin >> A >> B >> C;
    long long s = A.size();
    for (long long i = 0; i < s; i++)
    {
        long long a = A[i] - '0';
        long long b = B[i] - '0';
        long long c = C[i] - '0';
        // cerr << "a = " << a << endl;
        // cerr << "b = " << b << endl;
        // cerr << "c = " << c << endl;
        for (long long t = 0; t <= 9; t++)
        {
            if ((a + b + t) % 10 != c)
                continue;
            else
            {
                if (i > 0)
                    DP[i][t] = DP[i - 1][(a + b + t) / 10];
                if (a + b + t == c)
                    DP[i][t]++;
            }
        }
    }
    // for (long long i = 0; i < s; i++)
    // {
    //     for (long long t = 0; t <= 9; t++)
    //     {
    //         cerr << "DP[" << i << "][" << t << "] = " << DP[i][t] << endl;
    //     }
    //     cerr << endl;
    // }
    long long result = 0;
    for (long long i = 0; i < s; i++)
        result += DP[i][0];
    cout << result << endl;
}