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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD1 = 667676767;
const ll MOD2 = 129969137;

struct pair_hash {
    inline size_t operator()(const pair<ll, ll> & v) const {
        return v.first * 31 + v.second;
    }
};

ll power(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    string a, b, c;
    cin >> a >> b >> c;

    int n = a.size();
    vector<ll> invP1(n + 1), invP2(n + 1);

    ll inv10_1 = power(10, MOD1 - 2, MOD1);
    ll inv10_2 = power(10, MOD2 - 2, MOD2);
    
    invP1[0] = 1;
    invP2[0] = 1;
    for (int i = 1; i <= n; i++) {
        invP1[i] = (invP1[i - 1] * inv10_1) % MOD1;
        invP2[i] = (invP2[i - 1] * inv10_2) % MOD2;
    }

    // Mapa z parą jako kluczem i własnym haszerem
    unordered_map<pair<ll, ll>, int, pair_hash> counts;
    counts[{0, 0}] = 1;

    ll h1 = 0, h2 = 0;
    ll total_pairs = 0;

    for (int j = 0; j < n; j++) {
        int dj = (a[j] - '0') + (b[j] - '0') - (c[j] - '0');
        
        h1 = (h1 * 10 + dj) % MOD1;
        if (h1 < 0) h1 += MOD1;
        
        h2 = (h2 * 10 + dj) % MOD2;
        if (h2 < 0) h2 += MOD2;

        ll nh1 = (h1 * invP1[j + 1]) % MOD1;
        ll nh2 = (h2 * invP2[j + 1]) % MOD2;

        pair<ll, ll> current_pair = {nh1, nh2};

        if (counts.count(current_pair)) {
            total_pairs += counts[current_pair];
        }
        
        counts[current_pair]++;
    }

    cout << total_pairs << endl;

    return 0;
}