What are you asking for is not clear. you solved it or tried to solved it by dp and got TLE? And first describe you approach or give a link of your code. without this how can anyone tell you that what are you missing !!!!

it's better to use memo[20][7][7][7][2] because the length will not be greater than 20 and you shouldn't make the number of (3's , 6's , 9's ) more than 6 during calculation because it will not lead to positive result .

Immagine you have a accumulative array sum[N]:

sum[1] = sum[0] + C1;

sum[2] = sum[1] + C2;

....

sum[n] = sum[n-1] + C;

If you want to a sub-interval [L, R], you get it by sum[R] — sum[L-1]. You should do something similar as 369[B] — 369[A-1].

I think, it's not solvable by this dp. 50*16*16*16*2*100*10 = 409600000 is too high number of operations. Try to do it with combinatorics instead of dp. Now complexity is O(10·T·len⁴ / 27), I think, you can achieve O(10·T·len² / 3) with combinatorics.

Solution is: Take first x digits from number A, iterate (x+1)-th digit from 0 to A[x+1]-1 and count by combinatorics, how many numbers with such starting x + 1 digits can have exactly y threes, sixes and nines, where y is in range (1, len / 3). We have first x+1 digits, and last digits can be every number from 0 to 9, so we can count for every y the amount of possible numbers by combinatorics easily.

UPD: Code

I have just solved it. My time is 0.0 :D

I found this blog which gives a nice tutorial on how to solve this kind of problems.

here is my code.