Giả sử chúng ta có một lưới có kích thước là 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. Ở đây, các màu sẽ được sử dụng là Đỏ, Vàng và Xanh lục.
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. Cuối cùng, 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 =10 ^ 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, thực hiện 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)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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