2026牛客暑期多校3-F Not Aqre 2（状压DP，矩阵加速）
2026牛客暑期多校3-F Not Aqre 2（状压DP，矩阵加速）
题目：
F. Not Aqre 2
给定一个 n×m 的网格。你需要在每个格子中填入 、、0、1、2 中的一个整数。
如果任意两个共享一条边的格子填有不同的整数，则称该填法为好的。
输出好的填法数对 998244353 取模的结果。
输入格式
每个测试文件仅包含一组测试数据。
唯一一行包含两个整数 n 和 m ，(1≤n<10，1≤m<998244353)。
输出格式
输出一个整数表示答案。
样例
standard input
2 2standard output
18备注
在样例中，网格有 2 行 2 列。 第一列有 6 种选法：01,02,10,12,21,20。对于第一列的任意一种选法，第二列恰好有 3 种合法的选法。因此答案为6·3=18
题解
这道题是本场题目最短的，所以也是我开的第一道题。但这道题对我来讲还是太有难度了。想到了 dp 想到了矩阵加速，但是想不出来具体该怎么做。
题目大意
题意很好理解，给定矩阵行列数，元素只能为 、、1、2、3 其中之一，要求上下左右相邻的元素不同，求有多少种填法。
思考
这道题并不是直接的排列计数，对于单独的一列或一行很容易知道是一个排列计数，但因为是多行多列，其他的行有多少种合法状态需要由已有的行确定。
于是很容易就想到了动态规划。注意到 n 的值域很小，一列最多 3×28 种状态。可以记录每种状态当前有多少合法序列，每种合法序列可以与多少种不同的合法序列相邻，从而线性递推求解。但很明显 m 的值过大，这种方法不行。
对于线性时间复杂度的 dp，很容易想到的是利用矩阵乘法做线性变换，利用矩阵快速幂加速转换矩阵的变换，也就是矩阵加速（多帅的算法啊！）。但直接构建转换矩阵 T 的话，大小可以达到 (3×28)×(3×28)，因为每种状态都需要矩阵元素来记录，Tij=1 表示状态 i 可以与 状态 j 相邻。这显然不行，矩阵快速幂时间复杂度为 O(S3logm)。
我们的下一步当然是考虑优化算法了。可以注意到的一点是，我们没有必要记录每一个位置的具体数字是多少，我们关心的只有它们相同还是不同。对于当前位置 $i$，它要么是 $i-2$ 的数字，要么是 $i-1$ 和 $i-2$ 都不是的数字，也就是，相对于前两个位置，它只有两种情况。当最开始的两个位置确定，则对应的最多有 $2^7=128$ 种状态，太强了，居然压缩了这么多！
接下来我们不就可以用矩阵加速了吗。对于一个确定的前两个数字对应的 $128$ 种状态，我们计算初始矩阵 $T$，枚举相邻位置的可能的前两个数字，有 $6$ 种情况，每种情况对应 $128$ 个可能的状态，检查每种情况有多少种相邻状态是可行的。我们计算的是一种特殊起始数字对应的转移矩阵，一共有 $6$ 种起始态，我们只关心相对情况，因此每种起始态的答案是相等的，最后乘 $6$ 就可以了。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod = 998244353;
class mat {
public:
vector<vector<int>> dat;
int a,b;
mat(const int& a_, const int& b_) {
a = a_;
b = b_;
dat.resize(a+1, vector<int>(b+1,0));
}
mat operator*(const mat& m) const {
if (b!=m.a) {
return *this;
}
mat res(a, m.b);
for (int i=1;i<=a;++i) {
for (int j=1;j<=m.b;++j) {
for (int k=1;k<=b;++k) {
res.dat[i][j] += dat[i][k]*m.dat[k][j]%mod;
res.dat[i][j] = (res.dat[i][j]+mod)%mod;
}
}
}
return res;
}
};
mat mqp(mat a, int b) {
mat res(a.a,a.b);
for (int i=1;i<=a.a;++i) {
res.dat[i][i]=1;
}
while (b) {
if (b&1) {
res=res*a;
}
b>>=1;
a=a*a;
}
return res;
}
int qp(int a,int b) {
int res =1;
a%=mod;
while (b) {
if (b&1) {
res=res*a%mod;
}
b>>=1;
a=a*a%mod;
}
return res;
}
signed main() {
int n,m;
cin>>n>>m;
if (n==1) {
cout << 3ll*qp(2,m-1)%mod << "\n";
return 0;
}
const int maxk = 1ll<<(n-2);
mat T(maxk,maxk);
auto geta = [&](int a1,int a2, int k)->vector<int> {
vector<int> res(n+1);
res[1]=a1;
res[2]=a2;
for (int i=3;i<=n;++i) {
if ((k>>(i-3)&1)) {
res[i] = 3-res[i-1]-res[i-2];
}
else res[i] = res[i-2];
}
return res;
};
auto check = [&](const int& a, const int& b) -> int {
int cnt = 0;
int a1 = 0, a2 = 1;
vector<int> arr1 = geta(a1, a2, a);
for (int b1 = 0; b1 < 3; ++b1) {
if (b1 == arr1[1]) continue;
for (int b2 = 0; b2 < 3; ++b2) {
if (b1 == b2 || b2 == arr1[2]) continue;
vector<int> arr2 = geta(b1, b2, b);
bool ok = true;
for (int i = 1; i <= n; ++i) {
if (arr1[i] == arr2[i]) {
ok = false;
break;
}
}
if (ok) cnt++;
}
}
return cnt;
};
for (int i=0;i<maxk;++i) {
for (int j=0;j<maxk;++j) {
T.dat[i+1][j+1]+=check(i,j);
}
}
if (m==1) {
cout << maxk*6ll%mod << "\n";
return 0;
}
T = mqp(T, m-1);
int res=0;
for (int i=1;i<=maxk;++i) {
for (int j=1;j<=maxk;++j) {
res += T.dat[i][j];
res %= mod;
}
}
res = res*6ll%mod;
cout << res << "\n";
return 0;
}