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 | #include <iostream>
#include <vector>
using namespace std;
using ll = long long;
ll solve(const vector<int>& v) {
int n = v.size();
vector<ll> f(n+1);
f[n] = 1;
for (int i = n-1; i >= 0; --i) {
f[i] = (v[i]+1) * f[i+1];
if (v[i] == 1 && i+1 < n) {
int d = 10 + v[i+1];
f[i] += (1 + 18 - d) * f[i+2];
}
}
return f[0];
}
int main() {
ios_base::sync_with_stdio(0);
string s;
cin >> s;
vector<int> v;
for (auto x : s) {
v.push_back(x-'0');
}
auto res = solve(v);
cout << res << endl;
return 0;
}
|