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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using lld= long double;
#define v vector
#define pb  push_back
#define FF first
#define SS second
#define ALL(a) a.begin(), a.end()
v<ll>aa, bb, cc;
v<v<ll>>dp;
ll ans = 0;
void rob(ll indx, ll add = 0){
    if(indx < 0) return;
    if(dp[indx][add] != -1) {ans += dp[indx][add]; return;}
    dp[indx][add] = 0;
    if((aa[indx] + bb[indx] + add)%10 != cc[indx]){
        dp[indx][add] = 0;
        return;
    }
    if(indx != 0){
        ll pom = aa[indx]+bb[indx]+add >= 10 ? 1:0;
        rob(indx-1, pom);
        dp[indx][add] = dp[indx-1][pom];
    }
    if((aa[indx] + bb[indx] + add) < 10) {
        ans ++;
        dp[indx][add] ++;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    string a1, b1, c1;
    cin>>a1>>b1>>c1;
    for(char a : a1)
        aa.pb(a - '0');
    for(char a : b1)
        bb.pb(a - '0');
    for(char a : c1)
        cc.pb(a - '0');

    dp.resize(aa.size(), v<ll>(2, -1));
    for(ll i=aa.size()-1;i>=0;i--)
        rob(i);
    cout<<ans;
}