Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long ll;
typedef vector<ll> vl;

ll digitDP(ll tsum, int n){
  vector<vl> dp(n+1, vl(tsum+1,0) );
  dp[0][0] = 1;
  rep(i,n){
    rep(j,tsum+1){
      rep(k,10){
	int nj = j+k;
	if(nj>tsum)continue;
	dp[i+1][nj] += dp[i][j];
      }
    }
  }

  ll ans = 0;
  rep(i,tsum) ans += dp[n][i];

  return ans;
}

unordered_map<ll,ll> memo;
ll memoDP(int cur_step, ll cur_prod, ll cur_sum,
	  const ll tprod, const ll tsum, const int n){
  ll key = cur_prod*4000+cur_sum*20+cur_step;
  if(memo.count(key))return memo[key];

  if(cur_step == n){
    return (cur_sum == tsum && cur_prod < tprod) ? 1 : 0;
  }

  ll ans = 0;
  rep(i,10){
    if(cur_sum+i > tsum)break;
    if(cur_prod*(i+1) >= tprod)break;
    ans += memoDP(cur_step+1, cur_prod*(i+1), cur_sum+i, tprod, tsum, n);
  }

  return memo[key] = ans;
}

ll memoDP2(int cur_step, ll cur_prod, ll cur_sum, const string &d, ll flag,
	  const ll tprod, const ll tsum, const int n){
  ll key = cur_prod*6000+cur_sum*40+cur_step*2+flag;
  if(memo.count(key))return memo[key];

  if(cur_step == n){
    return (cur_sum == 0 && cur_prod == 1 && flag) ? 1 : 0;
  }

  ll ans = 0;
  rep(i,10){
    if(cur_sum-i < 0)continue;
    if(cur_prod%(i+1) != 0)continue;
    int k = d[cur_step]-'0';
    if(i==k){
      ans += memoDP2(cur_step+1, cur_prod/(i+1), cur_sum-i, d, flag, tprod, tsum, n);
    }else if(i<k){
      ans += memoDP2(cur_step+1, cur_prod/(i+1), cur_sum-i, d, 1, tprod, tsum, n);
    }else if(flag){
      ans += memoDP2(cur_step+1, cur_prod/(i+1), cur_sum-i, d, 1, tprod, tsum, n);
    }
  }

  return memo[key] = ans;
}

int main(){
  ll tsum = 0, tprod = 1, tint = 0;
  string d;
  cin >> d;
  int n = d.size();
  
  rep(i,n){
    ll dint = d[i]-'0';
    tsum += dint;
    tprod *= (dint+1);
    tint = tint*10 + dint;
  }

  ll ans = 0;
  ans += digitDP(tsum,  n);

  memo.clear();
  ans += memoDP(0, 1, 0, tprod, tsum, n);

  memo.clear();
  ans += memoDP2(0, tprod, tsum, d, 0, tprod, tsum, n);

  cout << ans << endl;
}