COUNT
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tèo nuôi \(N\) con chuồn chuồn, vì tinh nghịch nên Tèo dán lên mỗi con chuồn chuồn một số \(X (1 \le X \le 3)\). Sau khi dán xong, Tèo bỗng nhiên nãy ra một câu hỏi: "Có bao nhiêu cách dán các số lên các con chuồn chuồn sao cho tổng các số sau khi dán chia hết cho 3 ?".
Vì có quá nhiều con chuồn chuồn nên Tèo nhờ bạn giúp. Bạn hãy giúp Tèo giải câu hỏi trên nhé.
Input
- Gồm một dòng duy nhất chứa số nguyên \(N (1 \leq N \le 10^{18})\).
Output
- Gồm một số nguyên duy nhất là kết quả bài toán (Kết quả lấy phần dư cho \(10^9 + 7\)).
Example
Test 1
Input
2 Output
3Note
- Các cách đánh số các con chuồn chuồn là: \((1, 2), (2, 1), (3, 3)\).
Bình luận
Mình xin chia sẻ lời giải bài này như sau:
Gọi \(F[n]\) là số cách dán các số lên các con chuồn chuồn sao cho tổng các số sau khi dán chia hết cho \(3\).
Khi đó ta có công thức truy hồi sau: \(F[n]=3*F[n-1]=3^2*F[n-2]=...=3^{n-1}*F[1]\), với \(F[1]=1\). Do đó \(F[n]=3^{n-1}\)
Đến đây ta sử dụng luỹ thừa nhị phân là bài toán đã được giải quyết.
Độ phức tạp: \(O(log(n))\)
Các bạn có thể tham khảo code tại đây: Link
xin hint với ạ