TWICE9 (Super very hard)
Xem PDF
Điểm:
500 (p)
Thời gian:
0.5s
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, ai làm được có thưởng :v **
Một dãy FIBONACCI được định nghĩa như sau: \(F_{0}\) = \(F_{1}\) = 1; \(F_{N}\) = \(F_{N-1}\) + \(F_{N-2}\) \(\forall\) \(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}}\) \(\forall\) 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 5Output
2
2
1
2Note
- \(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_{4}\) = \(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
ai làm đc có thưởng :v mà k chơi lấy code fastest trong 2 cái kia nộp nha :v
a @vinhntndu thưởng điểm+rank 🙂
cố lên có j chỉ bài vs nha :V
lại xạo đi
:)) đó là làm đc
=))))