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 <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string a, b, c; cin >> a >> b >> c;
    int n = a.length();

    mt19937_64 rng(4206931415);
    vector<int> h(n + 1);
    for (int i = 0; i <= n; i++) h[i] = rng();

    vector<int> px(n + 1);
    unordered_map<int, int> cnt;
    cnt[0] = 1;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i] - '0';
        int y = b[i] - '0';
        int z = c[i] - '0';
        if (x + y >= 10) {
            // cout << i << " IF1\n";
            px[i + 1] ^= h[i];
        }
        if ((x + y + 1) % 10 == z) {
            // cout << i << " IF2\n";
            px[i + 1] ^= h[i + 1];
            if (x + y + 1 == 10) {
                px[i + 1] ^= h[i];
            }
        }
        else if ((x + y) % 10 != z) {
            // cout << i << " IF3\n";
            px[i + 1] ^= rng();
        }
        // cout << i << " " << px[i + 1] << "\n";
        px[i + 1] ^= px[i];
        // cout << i << " " << px[i + 1] << "\n";
        // if (cnt[px[i + 1]]) cout << "ADD " << i << "\n";
        ans += cnt[px[i + 1]]++;
    }
    cout << ans << "\n";
}