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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>

int DA[1000000];
int DB[1000000];
int DC[1000000];

int wczytaj(int* start)
{
  int* p = start;
  char c;
  while ((c = getchar()) != '\n') {
    *p++ = c - '0';
  }
  return p - start;
}

struct Policz
{
  // x = nie pasuje
  // n = pasuje normalnie
  // d = pasuje z przekroczeniem 9
  // t = pasuje z przeniesieniem 1

  long nnn = 0;
  long dnn = 0;
  long nnt = 0;
  long dnt = 0;

  long xnx = 0;

  long nnx = 0;
  long dnx = 0;
  
  long xnn = 0;
  long xnt = 0;
};

Policz policz(int l, int r) {
  // liczymy dla [l..r] włącznie

  Policz wynik;
  if (l == r) {
    // dla jednego miejsca
    
    int diff = DA[l] + DB[l] - DC[l];
    if (diff == 0) {
      wynik.nnn = 1;
    } else if (diff == 10) {
      wynik.dnn = 1;
    } else if (diff == -1) {
      wynik.nnt = 1;
    } else if (diff == 9) {
      wynik.dnt = 1;
    }
    
  } else {

    int m = (l + r) / 2;
    // dzielimy na przedziały [l..m] i [m+1..r]

    Policz p = policz(l, m);
    Policz q = policz(m+1, r);

    // te które przechodzą przez całość
    wynik.nnn = p.nnn * q.nnn + p.nnt * q.dnn;
    wynik.dnn = p.dnn * q.nnn + p.dnt * q.dnn;
    wynik.nnt = p.nnn * q.nnt + p.nnt * q.dnt;
    wynik.dnt = p.dnn * q.nnt + p.dnt * q.dnt;
    
    // tylko w środku, bez wychodzenia na brzegi
    wynik.xnx = p.xnx + q.xnx + p.xnn + q.nnx + p.xnn * q.nnx + p.xnt * q.dnx;

    // tylko na początku, nie dochodząc do końca
    wynik.nnx = p.nnn + p.nnx + p.nnn * q.nnx + p.nnt * q.dnx;
    wynik.dnx = p.dnn + p.dnx + p.dnn * q.nnx + p.dnt * q.dnx;
    
    // tylko na końcu, nie od początku
    wynik.xnn = q.nnn + q.xnn + p.xnn * q.nnn + p.xnt * q.dnn;
    wynik.xnt = q.nnt + q.xnt + p.xnn * q.nnt + p.xnt * q.dnt;
  }

  //printf("[%d..%d]: nnn=%ld\n", l, r, wynik.nnn);
  //printf("[%d..%d]: nnx=%ld\n", l, r, wynik.nnx);
  return wynik;
}

int main()
{
  const int N = wczytaj(DA);
  wczytaj(DB);
  wczytaj(DC);

  Policz p = policz(0, N-1);
  printf("%ld\n", p.nnn + p.nnx + p.xnn + p.xnx);

  return 0;
}