|
|
My solution is O(tl^3logn) , but its performance is good. 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 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). Can you give me some tests,please? I can't find any solutions on the internet. Edited by author 03.05.2021 09:14 Input: 2 100 2 20 1000000000000000000 2 100 Output: 184 967176416 |
|
|