Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<string>
#include<functional>
#include<unordered_map>
#include<map>
#include<tuple>
#include<utility>
using namespace std;
int main(int argc, char *argv[])
{
  string s;
  cin >> s;
  const int n = s.size();
  vector<int> ds;
  int sum = 0;
  long long prod = 1;
  for(int i = 0; i < n; i++) {
    ds.push_back(s[i]-'0');
    sum += ds.back();
    prod *= (ds.back() + 1);
  }
  // struct myhash : public std::unary_function<pair<long long,int>, std::size_t> {
  //   std::size_t operator()(const pair<long long,int>& k) const {
  //     return ((std::get<0>(k) & 0xffffffff) + ((std::get<0>(k) >> 32) & 0xffffffff))  + std::get<1>(k);
  //   }
  // };
  // vector<vector<unordered_map<pair<long long,int>,long long,myhash>>> mem(n+1, vector<unordered_map<pair<long long,int>,long long,myhash>>(10*n));
  vector<vector<map<pair<long long,int>,long long>>> mem(n+1, vector<map<pair<long long,int>,long long>>(10*n));

  function<long long(int,int,long long,int)> rec = [n,sum,prod,&ds,&rec,&mem](int k, int s, long long p, int cmp) {
    auto pcmp = make_pair(p,cmp);
    auto it = mem[k][s].find(pcmp);
    if(it != mem[k][s].end()) return it->second;
    long long cnt = 0;
    if(k == n) {
      if(s < sum
         || ((s == sum) && (p < prod))
         || ((s == sum) && (p == prod) && (cmp < 0))) cnt = 1;
      else cnt = 0;
    } else {
      // k-th digit
      for(int d = 0; d < 10; d++) {
        if(s + d > sum) break; // no more
        int dd = d - ds[k];
        if(dd < 0) dd = -1;
        if(dd > 0) dd = 1;
        cnt += rec(k+1, s+d, p*(d+1), cmp == 0 ? dd : cmp);
      }
    }
    mem[k][s][pcmp] = cnt;
    return cnt;
  };
  cout << rec(0, 0, 1, 0) << endl;
  
  return 0;
}