시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 76 | 11 | 8 | 13.115% |
Let us define the sequence of Fibonacci numbers as:
The first few elements of the sequence are 1, 2, 3, 5, 8, 13, 21, . . .
For a positive integer p, let X(p) denote the number of different ways of expressing p as a sum of different Fibonacci numbers. Two ways are considered different if there is a Fibonacci number that exists in exactly one of them.
You are given a sequence of n positive integers a1, a2, . . . , an. For a non-empty prefix a1, a2, . . . , ak, we define pk = Fa1 + Fa2 + . . . + Fak. Your task is to find the values X(pk) modulo 109 + 7, for all k = 1, . . . , n.
The first line of the standard input contains an integer n (1 ≤ n ≤ 100 000). The second line contains n space-separated integers a1, a2, . . . , an (1 ≤ ai ≤ 109).
The standard output should contain n lines. In the k-th line, print the value X(pk) modulo (109 + 7).
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | n, ai ≤ 15 |
2 | 20 | n, ai ≤ 100 |
3 | 15 | n ≤ 100, ai are squares of different natural numbers |
4 | 10 | n ≤ 100 |
5 | 15 | ai are different even numbers |
6 | 35 | No additional constraints |
4 4 1 1 5
2 2 1 2
We have the following values pk:
The number 5 can be expressed in two ways: as F2+F3 and simply as F4 (that is, 2+ 3 and 5, respectively). Hence, X(p1) = 2.
Then we have X(p2) = 2 because p2 = 1 + 5 = 1 + 2 + 3.
The only way to express 7 as a sum of different Fibonacci numbers is 2 + 5.
Finally, 15 can be expressed as 2 + 13 and 2 + 5 + 8 (two ways).