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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
m = 10^9 + 7
एक फ़ंक्शन add() परिभाषित करें, जो a, b लेगा,
((a mod m) + (b mod m)) mod 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) लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#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