Little Q is very wealthy and owns many coins. Little Q’s coins follow a pattern: for all non-negative integers K, Little Q has exactly two coins with the value 2^k. So Little Q owns coins of values 1, 1, 2, 2, 4, 4, and so on. Little Q needs to pay n money for something and wants to know how many different combinations of coins he can use to make this payment. Input: An integer n (1<=n<=10^18), representing the amount to be paid. Output: The number of ways Little Q can make this payment.

Reference solution:

#coding=utf-8
import math

n = int(input())

def getMaxCoin(n):
    tmp = int(math.log(n,2))
    return 2**tmp

buff = {}

def dp(n, coin):
    if (n, coin) in buff:
        return buff[(n,coin)]
    if n == 0: # Making change for 0 money is always possible
        return 1
    if coin == 1: # Only using 1-value coins
        if n == 1 or n == 2:
            return 1
        return 0 # No solution with current coin value
    if n > coin * 4 -2:
        return 0
    ret = 0
    # Using one coin of current value
    if n >= coin:
        ret += dp(n-coin, coin//2)
    if n >= coin*2:
    # Using two coins of current value
        ret += dp(n-coin*2, coin//2)
    # Not using any coin of current value
    ret += dp(n, coin//2)
    buff[(n,coin)] = ret
    return ret

print(dp(n,getMaxCoin(n)))

Approach: For the current amount, the maximum possible coin value that can be used is calculated by the getMaxCoin function. For the problem amount n and the maximum coin value that can be used, we calculate dp(n, coin). The coin value will continuously decrease. For coin value 1, there’s only 1 way to make amounts 1 or 2. For amount 0, no coins are needed for a solution. For amounts greater than coin*4-2, it exceeds the maximum possible value, so there’s no solution. For other cases, we consider three situations: using one coin of the current value, using two coins of the current value, or using zero coins of the current value. We calculate the corresponding dp values for each case. We use the buff cache to store already calculated values.