Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxL = 14;

ll dp[maxL+1][3][maxL*9+1][18601] = {0};

ll toLL(string str) {
	stringstream ss; ss << str;
	ll res; ss >> res;
	return res;
}
int main() {
	string strN; cin >> strN;
	ll N = toLL(strN);
	ll L = strN.size();
	set<ll> s[maxL+1];
	s[0].insert(1);
	for (ll i = 0; i < L; ++i) {
		for (set<ll>::iterator it = s[i].begin(); it != s[i].end(); ++it) {
			for (ll j = 1; j <= 10; ++j) {
				s[i+1].insert(*it * j);
			}
		}
	}
	ll ids = s[L].size();
	vector<ll> prods;
	for (set<ll>::iterator it = s[L].begin(); it != s[L].end(); ++it) {
		prods.push_back(*it);
	}
	map<ll, ll> tbl;
	for (ll i = 0; i < ids; ++i) {
		tbl[prods[i]] = i;
	}

	ll G[18601][10]; fill(G[0], G[18601], -1);
	for (ll i = 0; i < ids; ++i) {
		for (ll j = 0; j < 10; ++j) {
			ll v = prods[i]*(j+1);
			if (tbl.count(v) > 0) {
				G[i][j] = tbl[v];
			}
		}
	}

	dp[0][1][0][0] = 1;
	for (ll i = 0; i < L; ++i) {
		for (ll j = 0; j < 3; ++j) {
			for (ll ds = 0; ds <= L*9; ++ds) {
				for (ll k = 0; k < ids; ++k) {
					if (dp[i][j][ds][k]) {
						if (j == 1) {
							ll dl = strN[i]-'0';
							for (ll d = 0; d < 10; ++d) {
								ll nj = d > dl ? 2 : d == dl ? 1 : 0;
								dp[i+1][nj][ds+d][G[k][d]] += dp[i][j][ds][k];
							}
						}
						else {
							for (ll d = 0; d < 10; ++d) {
								dp[i+1][j][ds+d][G[k][d]] += dp[i][j][ds][k];
							}
						}
					}
				}
			}
		}
	}

	ll KK = 1; for (ll i = 0; i < L; ++i) KK *= (strN[i]-'0')+1;
	ll K = tbl[KK];
	ll DS = 0; for (ll i = 0; i < L; ++i) DS += strN[i]-'0';

	ll ans = 0;
	for (ll j = 0; j < 3; ++j) {
		for (ll ds = 0; ds <= DS; ++ds) {
			for (ll k = 0; k < ids; ++k) {
				if (ds < DS || (ds == DS && k < K) || (ds == DS && k == K && j != 2)) {
					ans += dp[L][j][ds][k];
				}
			}
		}
	}
	cout << ans-1 << endl;
}