Description
Cho một dãy N ô vuông xếp kề nhau. Tính số cách tô màu K ô sao cho không có hai ô vuông nào được tô màu nằm cạnh nhau.
Do kết quả có thể rất lớn nên chỉ cần in ra kết quả sau khi chia lấy dư cho 10^9+7.
Input:
Một dòng duy nhất ghi hai số nguyên N, K cách nhau bởi một dấu cách. Trong đó N≤\(10^9\),K≤5000
Output:
In ra đáp án sau khi chia lấy dư cho 10^9+7
Gợi ý:
Đánh số thứ tự các ô vuông . Đánh dấu các số liền nhau 1 đơn vị là False . Sau đó với các trường hợp còn lại là True thì đếm.
Bạn có thể cho mình một ví dụ được không?
cũng là dạng bài này nhưng mở rộng lên cho bảng m * n ô vuông và yêu cầu là đếm số cách tô k ô của bảng này sao cho ko có 2 ô vuông chung cạnh nào được tô. Bài này làm sao ạ, ai giúp em với