관영이의 취미는 장난감 저울을 가지고 노는 것이다. 관영이에겐 장난감 양팔 저울과 N종류의 무게추가 있다. 무게추는 서로 다르게 생겼기 때문에, 같은 무게의 무게추라도 서로 다르다. 각 종류마다 무게추는 무한히 있다고 가정한다.

관영이는 다 큰 고등학생이기 때문에, 그냥 무게추를 가지고 노는 것은 싫증이 나 버렸다. 그래서 관영이는 고등학생답게 함수 F(X)를 정의하고 그것을 더하며 놀기 시작했다. F(X)는 무게 X를 여러가지 추를 이용하여 재는 서로 다른 방법의 수이다. 예를 들어, 무게추가 1g, 1g, 2g 세 종류가 있다면, F(2) = 4가 된다. 두 1g 추가 서로 다르다는 점에 유의해서 다음을 보면 알 수 있다:

1g(1번 추)를 두개 쓴다.
1g(2번 추)를 두개 쓴다.
1g(1번 추)와 1g(2번 추)를 쓴다.
2g 추를 쓴다.

N개의 추의 무게와, L, R이 주어졌을 때, F(L)+F(L+1)+….+F(R)을 구하는 프로그램을 작성하라.

[부분문제의 제약 조건]

부분문제 1: 전체 점수 100점 중 42점에 해당하며 1 <= L <= R <= 10⁵이다.

부분문제 2: 전체 점수 100점 중 58점에 해당하며, 원래의 제약조건 이외에 아무 제약조건이 없다.

#3226 upload 7 done - how_to_reg -

장난감 저울 timer 2s memory 256MB

#3226

장난감 저울 2s 256MB