मान लीजिए कि हमारे पास आकार n x 3 का ग्रिड है और हम ग्रिड के प्रत्येक सेल को तीन रंगों में से एक के साथ पेंट करना चाहते हैं। रंग लाल, पीला या हरा हैं। अब एक बाधा है कि दो आसन्न कोशिकाओं का रंग समान नहीं है। हमारे पास ग्रिड की पंक्तियों की संख्या n है। हमें यह पता लगाना है कि हम इस ग्रिड को कितने तरीकों से पेंट कर सकते हैं। उत्तर बहुत बड़ा हो सकता है इसलिए इसे मॉड्यूलो 10^9 + 7 लौटाएं।
तो, अगर इनपुट 1 जैसा है, तो आउटपुट 12
. होगा 
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एम =1^9 + 7
-
फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,
. लगेगा -
वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम
-
मुख्य विधि से निम्न कार्य करें -
-
a123 :=6, a121 =6
-
इनिशियलाइज़ i :=2 के लिए, जब i <=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