💻
Elearning
CodePath
Problems
Contests
Roadmap
🐱 Scratch
🔐 Login
Lát dải ba loại
DP1_02_tile3
Bài 2. ### Đề bài Cần lát một dải dài `n`. Có `a` màu gạch dài 1, `b` màu gạch dài 2 và `c` màu gạch dài 3. Mỗi viên gạch được chọn độc lập theo màu. Hãy đếm số cách lát kín dải, modulo `1 000 000 007`. ### Dữ liệu vào Một dòng gồm `n a b c`. ### Kết quả Số cách lát kín dải. ### Ràng buộc `1 ≤ n ≤ 5·10^5`, `1 ≤ a,b,c ≤ 10^9`. ### Phân chia subtask | Subtask | Điểm | Ràng buộc | |---:|---:|---| | 1 | 30% | n ≤ 20 | | 2 | 30% | n ≤ 10^5 | | 3 | 40% | n ≤ 5·10^5 | ### Ví dụ **Input** ```text 4 1 1 1 ``` **Output** ```text 7 ``` **Giải thích:** Khi mỗi độ dài chỉ có một loại, số cách lát độ dài 4 là `7`.
✅ Đã AC: 2 / 2 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng