Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

constexpr ld eps = 1e-10;

constexpr int INF = 1e9;

constexpr int M = 1e9 + 7;

using graph = vector<vector<int>>;

int main() {
    string d;
    cin >> d;
    ll S = 0, P = 1;
    for(int i = 0; i < d.size(); ++i) {
        S += (d[i] - '0');
        P *= (d[i] - '0' + 1);
    }
    reverse(d.begin(), d.end());

    ll res = 0;
    map<tuple<int, ll, bool>, ll> dp; // (sum, prod, gt)
    dp[make_tuple(0, 1, false)] = 1;
    for(int i = 0; i < d.size(); ++i) {
        map<tuple<int, ll, bool>, ll> nxt;
        for(auto& t : dp) {
            int sum;
            ll prod;
            bool gt;
            tie(sum, prod, gt) = t.first;
            for(int j = 0; j <= 9; ++j) {
                int ns = sum + j;
                ll np = prod * (j + 1);
                bool ngt = (i == 0 ? true : gt) && (d[i] - '0') == j || (d[i] - '0') < j;
                if(ns > S || ns == S && np > P) {
                    continue;
                }
                nxt[make_tuple(ns, np, ngt)] += dp[t.first];
                if(i + 1 == d.size()) {
                    if(ns < S || ns == S && np < P || ns == S && np == P && !ngt) {
                        res += t.second;
                    }
                }
            }
        }
        dp = move(nxt);
    }
    cout << res << endl;
}