数据结构
网络
关系型数据库管理系统
操作系统
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 次浏览
广告