C++ में N×3 ग्रिड को रंगने के तरीकों की संख्या

समस्या विवरण

मान लीजिए हमारे पास n x 3 आकार का एक ग्रिड है और हम ग्रिड के प्रत्येक सेल को तीन रंगों में से ठीक एक से रंगना चाहते हैं। रंग हैं लाल, पीला या हरा। अब एक प्रतिबंध है कि कोई भी दो आसन्न सेल का रंग समान नहीं होना चाहिए। हमारे पास n ग्रिड की पंक्तियों की संख्या है। हमें उन तरीकों की संख्या ज्ञात करनी है जिनसे हम इस ग्रिड को रंग सकते हैं। उत्तर बहुत बड़ा हो सकता है इसलिए इसे 10^9 + 7 से मॉड्यूलो करके लौटाएं।

उदाहरण

यदि इनपुट है: 1, तो आउटपुट होगा 12

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (डायनामिक प्रोग्रामिंग):

m = 10^9 + 7
add() नामक एक फ़ंक्शन परिभाषित करें, जो a, b लेता है:
- ((a % m) + (b % m)) % m लौटाएं
मुख्य विधि से:
- a123 := 6, a121 = 6
- i := 2 से आरंभ करें, जब i <= n, i को 1 से बढ़ाते हुए:
  - b121 := add(3 * a121, 2 * a123)
  - b123 := add(2 * a121, 2 * a123)
  - a121 := b121
  - a123 := b123
- add(a123, a121) लौटाएं

C++ कार्यान्वयन

#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);
    }
};

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