수열

시간 제한1초메모리 제한1024 MB

요약

선형 점화식 A_i = A_{i-1} + A_{i-m}의 처음 m개 항이 주어질 때, A_p부터 A_q까지 홀수의 개수를 구한다. q는 2^60까지 커질 수 있다.

난이도: 어려움10점 중 9점
유형: 비트 연산, 수학, 동적 계획법, 행렬
정답자: 아직 제출이 없습니다

문제

수열 $\{A_n\}$ 은 $A_1$ 부터 $A_m$ 까지가 입력으로 주어지고, $i = m + 1$ 일 때 $A_i = A_{i-1} + A_{i-m}$ 을 만족한다. 이 수열의 제 $p$ 항부터 제 $q$ 항까지 $\{A_p, \ldots, A_q\}$ 에 포함된 홀수의 개수를 구하시오.

입력

1행에는 $m$ 이 주어진다. 2행에는 $p$ 가 주어진다. 3행에는 $q$ 가 주어진다. $i + 3$ 행 ( $1 \le i \le m$ )에는 $A_i$ 에 대응하는 값이 주어진다.

4행부터 $3 + m$ 행까지 주어지는 값은 음이 아닌 정수이며 $2\,000\,000\,000 = 2 \times 10^9$ 보다 작다. 또한 $2 \le m \le 24$ , $1 \le p < q \le 2^{60}$ 이다. $p, q$ 의 값이 32비트에 들어가지 않는다는 점에 주의하라.

출력

표준 출력으로 답을 출력한다. 주어진 범위에 포함된 홀수의 개수를 나타내는 정수를 출력하라.

예제2

예제 1
입력
```
4
2
8
1
2
3
4
```
예상 출력
```
3
```
예제 2
입력
```
3
1
100
0
0
0
```
예상 출력
```
0
```