C++プログラムでN×3グリッドをペイントする方法の数

ここで、2つの隣接するセルが同じ色を持たないという制約があります。グリッドの行数はn個です。最後に、このグリッドをペイントする方法の数を見つける必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法として返します。

したがって、入力が1のような場合、出力は12になります

これを解決するには、次の手順に従います-

• m =10 ^ 9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（（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