M-ary Partitions

We can solve the problem dynamically by solving dp(i,j) where i = value we're trying to obtain, and j = maximum exponent we're allowed to use. Assume b is the specified base.

dp(i,j) = sum(dp(i - x*b^j, j-1))

For the maximum base we're allowed to use, we simply iterate over all possible number of multiples we use that base. We subtract that off the number we're trying to obtain, and recurse using exponent - 1.

i < 10k, and j < log(10k) ~= 13, so the DP table is only 130k large. Iterating over all x is at most another 10^4, which puts us at >1 billion, but that worst case only occurs at a very small number of places in the table (namely when j is 2, and it's exponentially smaller than that in any other instance). So the solution should work fast enough.

max_ways[i]=sum(max_ways[