TWICE8 (Hard)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
vinhntndu
Dạng bài
Điểm: 700 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Lưu ý: Bản này khác bản dễ ở time limit và memory limit

Một dãy FIBONACCI được định nghĩa như sau: \(F_0 = F_1 = 1\); \(F_N = F_{N-1} + F_{N-2}\) \(∀\) \(N > 1\).

Một vài phần tử đầu của dãy là: 1,1,2,3,5,8,13,21,...

Với mỗi số nguyên dương \(p\), gọi \(D_p\) là số cách biểu diễn số \(p\) dưới dạng tổng các số FIBONACCI khác nhau.

Bạn được cho một mảng \(A\) gồm \(N\) phần tử. Với mỗi giá trị \(k\) = \(1, 2, ..., N\), ta định nghĩa \(p_k\) = \(F_{A_1} + F_{A_2} + ... + F_{A_k}\). Nhiệm vụ của bạn là hãy tính \(D_{p_k}\) \(∀\) \(k\) = \(1, 2, ... , N\). Vì kết quả rất lớn nên đáp án cuối cùng là \(D_{p_k}\) modulo \(10^9+7\).

Input

  • Dòng thứ nhất là số nguyên dương \(N\), số phần tử của mảng \(A\).
  • Dòng thứ hai gồm các số nguyên dương \(A_1, A_2, ... , A_N\).

Output

Gồm \(N\) dòng, mỗi dòng là \(D_{p_k}\) modulo \(10^9+7\).

Scoring

  • Subtask \(1\) (\(5\%\) số điểm): \(N, A_i \leq 15\).
  • Subtask \(2\) (\(20\%\) số điểm): \(N, A_i \leq 100\).
  • Subtask \(3\) (\(15\%\) số điểm): \(N \leq 100\), \(A_i\) là số chính phương.
  • Subtask \(4\) (\(10\%\) số điểm): \(N \leq 100\), \(A_i\) không có giới hạn gì thêm.
  • Subtask \(5\) (\(15\%\) số điểm): \(A_i\) là các số chẵn.
  • Subtask \(6\) (\(35\%\) số điểm): \(N \leq 10^5, A_i \leq 10^9\)

Example

Test 1

Input 
4
4 1 1 5
Output 
2
2
1
2
Note
  • \(p_1\) = \(F_4\) = 5
  • \(p_2\) = \(F_4\) + \(F_1\) = 5 + 1 = 6
  • \(p_3\) = \(F_4\) + \(F_1\) + \(F_1\) = 5 + 1 + 1 = 7
  • \(p_3\) = \(F_4\) + \(F_1\) + \(F_1\) + \(F_5\) = 5 + 1 + 1 + 8 = 15

Vậy ta có:

  • \(D_{P_1}\) = 2 (vì số 5 có thể biểu diễn bằng \(F_2 + F_3\) hay đơn giản là \(F_4\) )
  • \(D_{P_2}\) = 2 (vì 6 = 1 + 5 = 1 + 2 + 3)
  • \(D_{P_3}\) = 1 (vì số 7 chỉ có một cách biểu diễn duy nhất là 2 + 5)
  • \(D_{P_4}\) = 2 (vì 15 = 2 + 13 = 2 + 5 + 😎

Bình luận