Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	BIG,
	SMALL,
	SAME,
};

ll sequence[14],num_digit,sum,mult;
char buf[15];
map<ll,ll> MAP[15][127][3]; //MAP[桁][総和][type][tmp_mult] = 場合の数

ll recursive(int digit,ll tmp_sum,ll tmp_mult,Type type){

	if(MAP[digit][tmp_sum][type][tmp_mult] != 0)return MAP[digit][tmp_sum][type][tmp_mult];

	if(digit == num_digit){ //sequenceと同じ桁だけ動いた場合
		if(tmp_sum < sum){
			return 1;
		}else if(tmp_sum == sum && tmp_mult < mult){
			return 1;
		}else if(tmp_sum == sum && tmp_mult == mult && type == SMALL){
			return 1;
		}else{
			return 0;
		}
	}

	ll ret = 0,number = sequence[digit];

	for(ll next_num = 0; next_num <= 9; next_num++){
		if(type == SAME){
			if((tmp_sum+next_num > sum) || (tmp_sum+next_num == sum && tmp_mult*(next_num+1) > mult))break;

			if(next_num < number){
				ret += recursive(digit+1,tmp_sum+next_num,tmp_mult*(next_num+1),SMALL);
			}else if(next_num == number){ //next_num == number
				ret += recursive(digit+1,tmp_sum+next_num,tmp_mult*(next_num+1),SAME);
			}else{ //next_num > number
				ret += recursive(digit+1,tmp_sum+next_num,tmp_mult*(next_num+1),BIG);
			}
		}else if(type == SMALL){
			if((tmp_sum+next_num > sum) || (tmp_sum+next_num == sum && tmp_mult*(next_num+1) > mult))break;
			ret += recursive(digit+1,tmp_sum+next_num,tmp_mult*(next_num+1),SMALL);
		}else{ //type == BIG
			if((tmp_sum+next_num > sum) || (tmp_sum+next_num == sum && tmp_mult*(next_num+1) > mult))break;
			ret += recursive(digit+1,tmp_sum+next_num,tmp_mult*(next_num+1),BIG);
		}
	}

	return MAP[digit][tmp_sum][type][tmp_mult] = ret;
}

int main(){

	scanf("%s",buf);

	num_digit = 0;
	sum = 0;
	mult = 1;

	for(int i = 0; buf[i] != '\0'; i++){
		sequence[i] = (ll)(buf[i]-'0');

		sum += sequence[i];
		mult *= (sequence[i]+1);
		num_digit++;
	}

	printf("%lld\n",recursive(0,0,1,SAME));

	return 0;
}