Is there faster solution

My solution is O(tl^3logn) , but its performance is good.

Re: Is there faster solution

could you describe your solution? my algo O(logn * l^3 * t) has TL(

i try to find solution like this: dp[i, a, l] , i is bit number, a is addition to i-bit, l is lost count

Re: Is there faster solution

Yes, there is. (L^2)*log(N) solution (0.187 sec). I DP on total amount of coins and amount of extra coins for next denomination (the latter is used to know how much more can I push forward when I advance a digit). The first index always increases by K-1, the second always increases by K, so it's kind of diagonal partial summing up matrix to itself. If you precalculate reachable sums properly, you can perform DP transfer in O(L^2).