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
#include <bits/stdc++.h>

using namespace std;

template<typename T, T Base>
struct number
{
    vector<uint> digits;
    number() {}
    template<typename T1>
    number(T1 x)
    {
        while(x)
            digits.push_back(x % 10), x /= 10;
    }

    uint& operator() (size_t i)
    {
        while(digits.size() <= i)
            digits.emplace_back();
        return digits[i];
    }
    uint& operator[] (size_t i) { return digits[i]; }
    const uint& operator[] (size_t i) const { return digits[i]; }

    void normalize()
    {
        for(size_t i = 0; i < digits.size(); i++)
            if(digits[i] >= Base)
                operator()(i+1) += digits[i] / Base, digits[i] %= Base;
        while(not digits.back())
            digits.pop_back();
    }

    friend number operator+ (const number& a, const number& b)
    {
        if(a.digits.size() > b.digits.size()) return b + a;
        number c = b;
        for(size_t i = 0; i < a.digits.size(); i++)
            c[i] += a[i];
        c.normalize();
        return c;
    }
    friend number operator* (const number& a, const number& b)
    {
        number c;
        for(size_t i = 0; i < a.digits.size(); i++)
            for(size_t j = 0; j < b.digits.size(); j++)
                c(i+j) += a[i] * b[j];
        c.normalize();
        return c;
    }

    friend ostream& operator<< (ostream& out, const number& n)
    {
        for(size_t i = n.digits.size(); i --> 0; )
            out << n[i];
        return out;
    }
};

int main()
{
    map<string, uint> wae;
    for(uint a = 0; a <= 9; a++)
        for(uint b = 0; b <= 9; b++)
            wae[to_string(a + b)]++;

    string S;
    cin >> S;

    const size_t n = S.size();

    vector<number<uint, 10>> W(n+1);
    W[0] = 1;

    for(size_t i = 1; i <= n; i++)
        for(auto [k, v] : wae)
            if(i >= k.size() and S.substr(i-k.size(), k.size()) == k)
                W[i] = W[i] + number<uint, 10>(v)*W[i-k.size()];

    cout << W[n];
}