lx买东西

时间限制: 1000 ms 内存限制: 65536 kb

总通过人数: 1 总提交人数: 1

题目描述

BUAA有一台自动售货机，这台售货机只接收一种特殊硬币。这些硬币的价值是2的非负整数次幂(1, 2, 4, 8, 16, …)。硬币的价值没有大小限制。

例如，如果售货机要求付款7元，有下列付款方法：

7枚1元硬币

5枚1元硬币，1枚2元硬币

3枚1元硬币，2枚2元硬币

3枚1元硬币，1枚4元硬币

1枚1元硬币，3枚2元硬币

1枚1元硬币，1枚2元硬币，1枚4元硬币

现在lx每天都在这台售货机上买东西。他想知道使用这种特殊硬币付款$x$元的方法有多少种。

一行。一个小于等于200的正整数$x$，表示付款$x$元。

一行。一个整数，表示总方法数。