Giả sử chúng ta có lưới kích thước n x 3 và chúng ta muốn sơn mỗi ô của lưới với chính xác một trong ba màu. Màu sắc là Đỏ, Vàng hoặc Xanh lá cây. Bây giờ có một hạn chế là không có hai ô liền kề có cùng màu. Chúng ta có n số hàng của lưới. Chúng ta phải tìm số cách chúng ta có thể vẽ lưới này. Câu trả lời có thể rất lớn vì vậy hãy trả lại nó theo mô-đun 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là 1, thì đầu ra sẽ là 12
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
m =1 ^ 9 + 7
-
Xác định một hàm add (), điều này sẽ lấy a, b,
-
return ((a mod m) + (b mod m)) mod m
-
Từ phương thức chính, hãy làm như sau -
-
a123:=6, a121 =6
-
để khởi tạo i:=2, khi i <=n, cập nhật (tăng i lên 1), thực hiện -
-
b121:=add (3 * a121, 2 * a123)
-
b123:=add (2 * a121, 2 * a123)
-
a121:=b121
-
a123:=b123
-
-
trả về add (a123, a121)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli mod = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % mod) + (b % mod)) % mod;
}
int numOfWays(int n){
lli a123 = 6, a121 = 6;
lli b123, b121;
for (int i = 2; i <= n; i++) {
b121 = add(3 * a121, 2 * a123);
b123 = add(2 * a121, 2 * a123);
a121 = b121;
a123 = b123;
}
return add(a123, a121);
}
};
main(){
Solution ob;
cout << (ob.numOfWays(3));
} Đầu vào
3
Đầu ra
246