จำนวนวิธีทาสีกริด N×3 ใน C++

ปัญหา

กริดขนาด n × 3 ทาสีแต่ละเซลล์ด้วย 3 สี (แดง, เหลือง, เขียว) โดย เซลล์ติดกันไม่ bolehสีเดียวกัน (ติดกัน = แนวนอนหรือแนวตั้ง) หาจำนวนวิธีทาสี modulo 10^9 + 7

ตัวอย่าง: n = 1 → 12 วิธี

การวิเคราะห์รูปแบบแถว

แต่ละแถวมี 3 เซลล์ รูปแบบที่ถูกต้องมี 2 ประเภท:

• Type 123 (ABA pattern): สี 3 สีต่างกันหมด เช่น RGB, RBG, GRB, GBR, BRG, BGR → 6 แบบ
• Type 121 (ABA pattern): สีซ้าย-ขวาเหมือนกัน กลางต่าง เช่น RGR, GBG, ... → 6 แบบ

รวม 12 แบบสำหรับแถวเดียว

Transition ระหว่างแถว

กำหนด: - a123 = จำนวนวิธีจนถึงแถวปัจจุบัน ที่แถวปัจจุบันเป็น Type 123 - a121 = จำนวนวิธีจนถึงแถวปัจจุบัน ที่แถวปัจจุบันเป็น Type 121

จาก Type 123 (ABC) ไปแถวถัดไป:

• เป็น Type 123 ได้ 2 แบบ (ต้องสลับสีทั้ง 3 ตัว)
• เป็น Type 121 ได้ 2 แบบ

จาก Type 121 (ABA) ไปแถวถัดไป:

• เป็น Type 123 ได้ 2 แบบ
• เป็น Type 121 ได้ 3 แบบ

Recurrence

b121 = 3*a121 + 2*a123
b123 = 2*a121 + 2*a123

โค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli MOD = 1e9 + 7;

class Solution {
    lli add(lli a, lli b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
    
public:
    int numOfWays(int n) {
        lli a123 = 6, a121 = 6;  // n=1
        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);
    }
};

int main() {
    Solution ob;
    cout << ob.numOfWays(3);  // 246
    return 0;
}

ตารางค่าตัวอย่าง

ความซับซ้อน

• Time: O(n)
• Space: O(1)

Input / Output

Input:  3
Output: 246