AcWing 2560. 矩阵计数
原题链接
中等
作者:
CrSeven
,
2022-05-14 17:11:48
,
所有人可见
,
阅读 176
/*
f[i][j][k] 表示前i行已经摆好,且第i行的状态为j, 第i-1行的状态为k的方案数
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 6, M = 1 << N;
int f[N+2][M][M];
vector<int>state;
int n, m;
bool check(int x)
{
for(int i = 0; i < m; i++)
if((x >> i & 1) && (x >> i + 1 & 1) && (x >> i + 2 & 1))
return false;
return true;
}a
int main()
{
cin >> n >> m;
for(int i = 0; i < 1 << m; i++){
if(check(i)){
state.push_back(i);
}
}
int sz = state.size();
f[0][0][0] = 1;
for(int i = 1; i <= n+2; i++){
for(int j = 0; j < sz; j++){
for(int k = 0; k < sz; k++){
for(int u = 0; u < sz; u++){
bool flag = true;
int a = state[j], b = state[k], c = state[u];
for(int tx = 0; tx < m; tx++){
if((a >> tx & 1) && (b >> tx & 1) && (c >> tx & 1)) flag = false;
}
if(flag){
f[i][a][b] += f[i-1][b][c];
}
}
}
}
}
cout << f[n+2][0][0] << endl;
return 0;
}