資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 次瀏覽
廣告