Nhảy lò cò
Xem PDFCarnaval Hạ Long 2015 với chủ đề “Hội tụ tinh hoa - Lan tỏa nụ cười”, điểm mới của lễ hội là sự song hành giữa biểu diễn nghệ thuật “Nơi tinh hoa hội tụ” và diễu hành đường phố “Nụ cười Hạ Long” với sự góp mặt của hơn 2000 diễn viên quần chúng. Có rất nhiều chương trình vui chơi được tổ chức, một trong những trò chơi thu hút được nhiều du khách tham gia đó là trò chơi nhảy lò cò, cụ thể: người chơi cần vượt qua một đoạn đường dài \(n\) mét, mỗi bước, người chơi có ba cách nhảy với độ dài bước nhảy tương ứng là 1 mét, 2 mét, 3 mét. Một cách đi chuyển đúng là dãy các bước nhảy có tổng đúng bằng \(n\).
Yêu cầu: Cho \(n\) và \(M\), gọi \(K\) là số cách di chuyển đúng khác nhau để đi hết đoạn đường \(n\) mét, hãy tính phần dư của \(K\) chia \(M\).
Input
- Gồm một dòng chứa hai số nguyên dương \(n, M (M \le 20^{15})\);
Output
- Một số nguyên là phần dư của \(K\) chia \(M\).
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\);
- Subtask \(2\) (\(40\%\) số điểm): \(n \le 10^6\);
- Subtask \(3\) (\(40\%\) số điểm): \(n \le 10^{15}\).
Example
Test 1
Input
5 100 Output
13
Bình luận
bruh
Mình xin chia sẻ lời giải bài này như sau:
Gọi \(F[n]\) là số cách di chuyển đúng khác nhau để đi hết đoạn đường \(n\) mét. Khi đó, ta dễ dàng suy luận ra được \(F[n]=F[n-1]+F[n-2]+F[n-3](\forall n\ge 3)(1)\) với \(F[1]=1,F[2]=2,F[4]=4\) .
Đến đây, ta sử dụng nhân ma trận như sau:
Từ \((1)\implies \begin{pmatrix}F[n-1] & F[n] & F[n+1]\end{pmatrix}.\begin{pmatrix}0 & 0 &1 \\1 & 0 & 1\\0 & 1 &1\end{pmatrix}=\begin{pmatrix}F[n] & F[n+1] & F[n+2]\end{pmatrix}\)
Gọi \(p_n=\begin{pmatrix}F[n] & F[n+1] & F[n+2]\end{pmatrix}\) và \(M=\begin{pmatrix}0 & 0 &1 \\1 & 0 & 1\\0 & 1 &1\end{pmatrix}\).
Ta suy ra được \(p_n=p_{n-1}.M=...=p_1.M^{n-1}\), trong đó: \(p_1=(1,2,4)\)
Đến đây, ta chỉ việc sử dụng luỹ thừa nhị phân và nhân ma trận là xong.
Các bạn có thể tham khảo code tại đây: Link