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
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B, C;
    cin >> A >> B >> C;
    int n = A.size();

    const ll p1 = 1000000007LL;
    const ll p2 = 1000000009LL;

    vector<ll> pw1(n), pw2(n);
    pw1[0] = pw2[0] = 1;
    for (int j = 1; j < n; j++) {
        pw1[j] = pw1[j-1] * 10 % p1;
        pw2[j] = pw2[j-1] * 10 % p2;
    }

    unordered_map<ll, ll> cnt;
    cnt.reserve(1 << 21);
    cnt[0]++;

    ll s1 = 0, s2 = 0, ans = 0;
    for (int k = 1; k <= n; k++) {
        int e = (A[k-1]-'0') + (B[k-1]-'0') - (C[k-1]-'0');
        ll e1 = ((ll)e % p1 + p1) % p1;
        ll e2 = ((ll)e % p2 + p2) % p2;
        s1 = (s1 + e1 * pw1[n-k]) % p1;
        s2 = (s2 + e2 * pw2[n-k]) % p2;
        ll key = s1 * p2 + s2;
        ans += cnt[key];
        cnt[key]++;
    }

    cout << ans << "\n";
}