Hướng dẫn cho Dãy số Sussy

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: flo

Các bạn nên thử suy nghĩ cách giải trước khi xem hướng dẫn nhé

Subtask $1$ : $1 \le n \le 10^6$ .

Hint

Quy hoạch động.

Solution

Ta sẽ tính trước các giá trị $S_n$ với $1 \le n \le 10^6$ . Với mỗi số nguyên dương $n$ , ta chỉ cần in kết quả trong $O(1)$ .
Độ phức tạp của ý tưởng trên là $O(10^6 + t)$ .

Subtask $2$ : Không giới hạn gì thêm.

Hint

Dãy số Fibo như trong đề bài.

Solution

Theo đề, ta có:
$S_n = S_{n-1}+S_{n-2}+S_{n-1}\times S_{n-2}$ .
$= S_{n-1}+S_{n-2}+S_{n-1}\times S_{n-2}+1-1$ .
$= (S_{n-1}+1)\times (S_{n-2}+1)-1$ .
$= ((S_{n-2}+1)\times (S_{n-3}+1)-1+1)\times (S_{n-2}+1)-1$ .
$= (S_{n-2}+1)^2\times (S_{n-3}+1)-1$ .
$= ((S_{n-3}+1)\times (S_{n-4}+1)-1+1)^2\times (S_{n-3}+1)-1$ .
$= (S_{n-3}+1)^3\times (S_{n-4}+1)^2-1$ .
$= ...$
Ta nhận thấy rằng khi ta liên tục lặp lại điều trên, các số mũ của chúng sẽ tạo ra dãy số Fibo. Vì vậy ta có công thức sau.
$S_n= (S_1+1)^{F_{n-2}}\times (S_2+1)^{F_{n-1}}-1$ .
$= 70^{F_{n-2}}\times 420^{F_{n-1}}-1$ .
Vậy để tính $S_n$ , ta chỉ cần sử dụng nhân ma trận hoặc toán để tính $F_{n-2}$ và $F_{n-1}$ . Sau đó là sử dụng lũy thừa nhị phân để tìm kết quả.
Kết quả của chúng ta sẽ là $S_n = (70^{F_{n-2}}\times 420^{F_{n-1}}-1)$ $mod$ $2^{32}-3$ . Tuy nhiên $F_{n-1}$ và $F_{n-2}$ sẽ rất là lớn bởi hàm Fibo là hàm tăng vô cùng nhanh. Vì vậy ta cũng cần chia lấy dư cho $F_{n-1}$ và $F_{n-2}$ .

Warning

Để chia lấy dư cho $F_{n-1}$ và $F_{n-2}$ đúng thì ta sẽ sử dụng định lý Euler.

Bình luận

Không có bình luận nào.