题解 | #拼凑硬币#

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static Map<Long, Long> mem;

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            solution(in);
        }
    }

    /**
     * 数学法
     * 
     * f(n)表示凑成n元的方案数
     * 方案数即是不同的解向量[x1,x2,x3,x4,...]的个数
     *
     * 1. n为奇数(1种情况)
     * 必需使用一个1元钱
     * n = 1+2*x1+2*x2+4*x3+4*x4+...
     * f(n)=f(n−1)=f((n−1)/2)=f(n/2)=f(n>>1) (n为奇数)
     *
     * 2. n为偶数(2种情况)
     * (1) 不使用两个1元钱
     * n = 2*x1+2*x2+4*x3+4*x4+...
     * f(n)=f(n/2)=f(n>>1)
     *
     * (2) 同时使用两个1元钱
     * n = 1+1+2*x1+2*x2+4*x3+4*x4+...
     * f(n)=f(n-2)=f((n−2)/2)=f(n/2-1)=f((n>>1)-1)
     *
     * f(n)=f(n>>1)+f((n>>1)-1) (n为偶数)
     *
     * 综上可知:
     * 
     *        { f(n>>1)            , (n为奇数)
     * f(n) = {
     *        { f(n>>1)+f((n>>1)-1), (n为偶数)
     *        
     * @param in
     */
    private static void solution(Scanner in){
        long n = in.nextLong();

        mem = new HashMap<>();
        mem.put(1L, 1L);
        mem.put(2L, 2L);

        long result = dp(n);

        System.out.println(result);
    }

    /**
     * 动态规划
     * 
     * dp(i)表示凑成i元的方案数
     *
     *         { dp(i>>1)             , (n为奇数)
     * dp(i) = {
     *         { dp(i>>1)+dp((i>>1)-1), (n为偶数)
     * 
     * @param num
     * @return
     */
    private static long dp(long num){
        if(mem.containsKey(num)){
            return mem.get(num);
        }

        long count;
        if(isOdd(num)){
            count = dp(num>>1);
        }else{
            count = dp(num>>1) + dp((num>>1)-1);
        }

        mem.put(num, count);

        return count;
    }

    /**
     * 是否奇数
     * @param num
     * @return
     */
    private static boolean isOdd(long num){
        return ((num&1) == 1);
    }

    /**
     * 是否偶数
     * @param num
     * @return
     */
    private static boolean isEven(long num){
        return ((num&1) == 0);
    }
}