Hi all,

I recently tried solving this problem: Beautiful Numbers (url: http://www.codeforces.com/contest/55/problem/D).

I managed to get it AC( solution: http://pastebin.com/0kBFqTqu)

However, I am not sure why it works. In my initial solution, I need to reset my DP array each time, because I thought that my answer will change for different As and Bs. However, it seems that I will still give the correct answer even if I do not reset my arrays! Does anyone know why?

EDIT: More info about my dp

My DP recursion is f (prefix, N, LCM, five, seven, eight, nine)

This will return the number of beautiful numbers between A and B in the range prefix*10^N to prefix * (10^(N+1)-1), whose prefix has a lowest common multiple of LCM, and has remainder five when divided by 5, remainder seven when divided by 7 and so on ...

My dp array is dp[N][LCM][five][seven][eight][nine]. This is due to the observation that if N,LCM, five, seven, eight and nine are kept constant, then all prefixes, if their range (defined as prefix*10^N to prefix * (10^(N+1)-1)) is within A and B, will give the same answer. Therefore, I can reduce the number of states in my DP.

As you can see, the variables A and B are included in my definition of my DP. Therefore, I thought that once A and B changed, I will have to reset my arrays and work out the answers again. However, it seems that I do not have to do so! Does anyone know why?