C++ 中 N × 3 網格的著色方法數

假設我們有一個大小為 n x 3 的網格，我們希望用三種顏色中的每一種來繪製網格的每個單元格。這些顏色是紅色、黃色或綠色。現在有一個約束條件，即沒有兩個相鄰的單元格具有相同的顏色。我們有 n 表示網格的行數。我們必須找到可以繪製此網格的方法數。答案可能非常大，因此將其返回模 10^9 + 7。

因此，如果輸入類似於 1，則輸出將為 12

為了解決這個問題，我們將遵循以下步驟 -

  • m = 1^9 + 7

  • 定義一個函式 add()，它將接收 a、b，

  • 返回 ((a mod m) + (b mod m)) mod m

  • 從主方法執行以下操作 -

  • a123 := 6, a121 = 6

  • 對於初始化 i := 2，當 i <= n 時，更新（增加 i），執行 -

    • 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

更新於: 2020年6月9日

251 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告