สมมติว่าเรามีตารางขนาด n x 3 และเราต้องการลงสีแต่ละเซลล์ของตารางด้วยหนึ่งในสามสี มีสี แดง เหลือง หรือเขียว ขณะนี้มีข้อจำกัดที่ไม่มีเซลล์ที่อยู่ติดกันสองเซลล์ที่มีสีเหมือนกัน เรามีจำนวนแถวของตาราง n เราต้องหาหลายวิธีที่จะลงสีตารางนี้ได้ คำตอบอาจมีขนาดใหญ่มาก ให้คืนค่าเป็นโมดูโล 10^9 + 7.
ดังนั้นหากอินพุตเท่ากับ 1 เอาต์พุตจะเป็น 12
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม =1^9 + 7
-
กำหนดฟังก์ชัน add() ซึ่งจะใช้เวลา a, b,
-
กลับ ((a mod m) + (b mod m)) mod m
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
a123 :=6, a121 =6
-
สำหรับการเริ่มต้น i :=2 เมื่อฉัน <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
b121 :=เพิ่ม (3 * a121, 2 * a123)
-
b123 :=เพิ่ม (2 * a121, 2 * a123)
-
a121 :=b121
-
a123 :=b123
-
-
กลับเพิ่ม (a123, a121)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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));
} อินพุต
3
ผลลัพธ์
246
