Sumsets 2 1s 64MB

Problems

임의의 숫자 N이 주어졌을 때 2의 제곱수들의 합이 N이 되는 경우가 총 몇 가지가 있는지 알아내는 프로그램을 작성하라.

예를 들어 N = 7일 경우는 다음과 같이 6 가지가 존재한다.

1. 1+1+1+1+1+1+1

2. 1+1+1+1+1+2

3. 1+1+1+2+2

4. 1+1+1+4

5. 1+2+2+2

6. 1+2+4

첫 번째 줄에 정수 N 이 입력된다. (1 \le N \le 1,000,000)

첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,007으로 나눈 나머지를 출력한다.

Tag

USACO January 2005 Silver 1번

You must sign in to write code.