Problem:
Problem E
Bringing Order to Disorder A sequence of digits usually represents a number, but we may define an alternative interpretation. In this problem we define a new interpretation with the order relation $\prec$ among the digit sequences of the same length defined below. Let $s$ be a sequence of $n$ digits, $d_1d_2 ... d_n$, where each $d_i$ $(1 \leq i \leq n)$ is one of 0, 1, ... , and 9. Let sum($s$), prod($s$), and int($s$) be as follows:  sum($s$) = $d_1 + d_2 + ... + d_n$ prod($s$) = $(d_1 + 1) \times (d_2 + 1) \times  ... \times (d_n + 1)$ int($s$) = $d_1 \times 10^{n-1} + d_2 \times 10^{n-2} + ... + d_n \times 10^0$  int($s$) is the integer the digit sequence $s$ represents with normal decimal interpretation. Let $s_1$ and $s_2$ be sequences of the same number of digits. Then $s_1 \prec s_2$ ($s_1$ is less than $s_2$) is satisfied if and only if one of the following conditions is satisfied.  sum($s_1$) $<$ sum($s_2$)  sum($s_1$) $=$ sum($s_2$) and prod($s_1$) $<$ prod($s_2$)  sum($s_1$) $=$ sum($s_2$), prod($s_1$) $=$ prod($s_2$), and int($s_1$) $<$ int($s_2$)  For 2-digit sequences, for instance, the following relations are satisfied.  $00 \prec 01 \prec 10 \prec 02 \prec 20 \prec 11 \prec 03 \prec 30 \prec 12 \prec 21 \prec ... \prec 89 \prec 98 \prec 99$  Your task is, given an $n$-digit sequence $s$, to count up the number of $n$-digit sequences that are less than $s$ in the order $\prec$ defined above. Input The input consists of a single test case in a line.  $d_1d_2 ... d_n$  $n$ is a positive integer at most 14. Each of $d_1, d_2, ...,$  and $d_n$ is a digit. Output Print the number of the $n$-digit sequences less than $d_1d_2 ... d_n$ in the order defined above. Sample Input 1 20 Sample Output 1 4 Sample Input 2 020 Sample Output 2 5 Sample Input 3 118 Sample Output 3 245 Sample Input 4 11111111111111 Sample Output 4 40073759 Sample Input 5 99777222222211 Sample Output 5 23733362467675

Solution (Python):
def solve():
    D = input()
    N = len(D)
    *DI, = map(int, D)
    su = sum(DI)
    pd = 1
    for d in D:
        pd *= int(d) + 1
    memo = [{} for i in range(N)]
    def dfs0(i, s, p):
        key = (s, p)
        if i == N:
            return s > 0 or (s == 0 and p < pd)
        if key in memo[i]:
            return memo[i][key]
        r = 0
        for v in range(min(s, 9)+1):
            r += dfs0(i+1, s-v, p*(v+1))
        memo[i][key] = r
        return r
    res1 = dfs0(0, su, 1)
    memo1 = [{} for i in range(N)]
    def dfs1(i, s, p, m):
        key = (s, p, m)
        if i == N:
            return s == 0 and p == 1
        if key in memo1[i]:
            return memo1[i][key]
        r = 0
        b = s - (N-1-i)*9
        di = DI[i]
        for v in range(max(b, 0), min(s, 9)+1):
            if p % (v+1):
                continue
            if m == 0:
                if di < v:
                    break
                r += dfs1(i+1, s-v, p//(v+1), +(v < di))
            else:
                r += dfs1(i+1, s-v, p//(v+1), 1)
        memo1[i][key] = r
        return r
    res2 = dfs1(0, su, pd, 0) - 1
    ans = res1 + res2
    print(ans)
solve()