AcWing 4406. 积木画
原题链接
中等
作者:
修马宝莉别学了好吗
,
2024-04-09 10:53:31
,
所有人可见
,
阅读 4
/*
状态表示: f[i][j] 表示在 i 列 j 状态时候,且i - 1列前全部摆满,所有的摆法的集合
状态转移:f[i][j] += f[i - 1][j] * g[j][k]; //这个表示从f[i - 1][j] 乘以这个状态矩阵,
如果值为一就能判断能否转移到g[j][k]状态,如果能转移就用是等价于 1 * f[i][j]
输出状态:f[n][0];
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e7 + 10, MOD = 1000000007;
int f[2][4];
int g[4][4] = { // 这个转移方程一维有四个元素,分别对应0, 1, 2, 3 这个四种状态。
{1, 1, 1, 1}, // 用十进制表示二进制可以了解一下 bitmask 状态压缩
{0, 0, 1, 1}, // 二维数组4个元素也是这四种状态,表示一维数转移到该状态有多少种情况
{0, 1, 0, 1},
{1, 0, 0, 0}
};
int main() {
int n;
cin >> n;
f[0][0] = 1;
for (int i = 1; i <= n; i++){
memset(f[i & 1], 0, sizeof f[i & 1]);// 这里直接用memset比较方便
for (int j = 0; j < 4; j++) // 这里用 j 代表新状态
for (int k = 0; k < 4; k++) // 用 k 代表旧状态
//这个方程把所有能从k状态转移到j状态的情况都加到集合里面
f[i & 1][j] = (f[i & 1][j] + f[(i - 1) & 1][k] * g[k][j]) % MOD;
} // i & 1 就是 相当于 i % 2,两个数一个循环
cout << f[n & 1][0];
return 0;
}