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.
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
