#USACO114. Sumsets S
Sumsets S
[USACO05JAN] Sumsets S
题目描述
给出一个整数 ,将 分解为若干个 的次幂的和,共有多少种方法?
输入格式
输入一个整数 ()。
输出格式
输出方案数对 取模的结果。
样例 #1
样例输入 #1
7
样例输出 #1
6
提示
所有合法方案如下:
- 1+1+1+1+1+1+1
- 1+1+1+1+1+2
- 1+1+1+2+2
- 1+1+1+4
- 1+2+2+2
- 1+2+4
给出一个整数 N,将 N 分解为若干个 2 的次幂的和,共有多少种方法?
输入一个整数 N(1≤N≤106)。
输出方案数对 109 取模的结果。
7
6
所有合法方案如下: