First notice that the product of digits of x is always less than x, so that you actually have a DAG. Now the graph is defined by a single relation x->P(x), so we, in fact, have a tree (well, a forest). Why don't you explicitly build the forest for whatever your range is (I'm assuming it's small, because you asked about DP)? Maybe then you can visualize it easier.

For example, if it's a single query (N,v) it's enough to run a dfs from v. If you need a lot of queries and MAX_x < 10^5 or so then you can use sack ("dsu on tree") with an order statistic set on each node so each node knows all of its children and how many are less than N. And so on.

Auto comment: topic has been updated by vamaddur (previous revision, new revision, compare).

You can sort the digits first and the answer doesn't change. The number of the possible sorted sequence of digits is not too big so we can enumerate them all.

It is easy to understand that two numbers with the same digits (not necessarily with the same order, for example 1244, 4214) have the same answer. There are 10^13 different nums, but there are only about 700000 different sets of digits (you can calc it using this) So we can find all different sets. How to count numbers we can create from a certain set, that are <= N? Assume function f for set S (it contains pair of {digit, its count in number}) which returns count of different numbers we can create from S (not necessarily <= N), something like this:

int C(int n, int k){
    return fact[n] / (fact[k] * fact[n - k]);
}
int f(vector <pair <int, int> > s){
    int res = 1, left = 0;
    for (auto i : s) left += i.second;
    for (auto i : s){
        res *= C(left, i.second);
        left -= i.second;
    }
    return res;
}

It's easy to find count of numbers we can create from S, which length is less than length of N, but how we can solve case with equal length? We'll go with i for digits of N, current digit is a[i]. 1) We need to put digit x < a[i], now result number is always less than N, so we can decrease count of x and add to result f(new set), then increase count of x to get back (we need to do this with all x < a[i] we have). 2) If we have a[i] in our set, we need to put it (and decrease its count) and continue, otherwise break. Then add to ans[p_repeat(product of all digits in S)] our result. We need to make it with all different sets, and then print ans[v].

I have a solution without dynamic programming (though, I don't have solution with dynamic programming).

Let f(x) = P_repeat(x) (because the function name is too long), f(x) = f(P(x)) = f(P(P(x))) = ... = P(P(P(... P(x)... ))).

The main idea is, f(a) = f(b), if b is a non-leading-zero integer that scrambled a, because obviously P(a) = P(b), so f(a) = f(P(a)) = f(P(b)) = f(b). So, you can brute-force the number of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 digits.

Let's consider counting the number of x that f(x) = v, in range of 10^b ≤ x ≤ n. Let c_i the number of i's (0 ≤ i ≤ 9) in x, it satisfies 0 ≤ c_i, and c₀ + c₁ + c₂ + ... + c₉ = b + 1. The way is C(b + 10, 9). If b = 12 (maximum), there are only 497420 ways.

Let f(c₀, c₁, ..., c₉) the value of f(x) if x has c₀ 0's, c₁ 1's, c₂ 2's,... . If f(c₀, c₁, ..., c₉) = v, you can add "the number of integers less or equal to n, which has c₀ 0's, c₁ 1's, c₂ 2's,..." to the answer.

And how can calculate "the number of integers less or equal to n, which has c₀ 0's, c₁ 1's, c₂ 2's,..."? Let's consider about the problem.

How many integers which has two 1's and two 2's and one 3, less than 22331?