毒瘤题啊

首先考虑如果询问的是有多少种连线方案，那么每个点有 2 种状态，可以直接状压出答案，但是这题询问的是染色方案，一个染完色的图可能对应很多种不同的连线方案。换句话说，我们没法去掉被重复计算的方案。

如果把加入新一列染色看作转移，连线的方案看作是状态，那么这种一种转移对应多种状态就叫做非确定有限状态自动机 NFA。通常的 dp 套 dp 都是在有限状态自动机 DFA 上转移的。

考虑一个通用的把 NFA 转化为 DFA 的方法子集构造法，如果 NFA 上的两个状态能够转移到的状态是完全一样的，我们就称他们为等价的，将等价的状态都塞进一个新的 DFA 状态里，就构成一个 DFA。易知 DFA 的状态一定是一个 NFA 状态集的子集。

本题的连线，每个格子有以下五种状态：

1. 和当前列格子没有边。
2. 上一列格子的 1 连着当前列格子的 2。
3. 上一列格子的 3 连着当前列格子的 2。
4. 上一列格子的 2 连着当前列格子的 1。
5. 上一列格子的 2 连着当前列格子的 3。

那么NFA有 $5^3$ 种状态，难道DFA有 $2^{5^3}$ 种状态吗？爆搜加打表可知，最多只有 46 种状态，最后建出转移矩阵即可。

#include<bits/stdc++.h>
using namespace std;

#define int long long 

const int N=1e5+5,mod=998244353;

bool st;
//0 已匹配
//1 2要与1匹配
//2 2要与3匹配
//3 1要与2匹配
//4 3要与2匹配
struct matrix{
	int n,m;
	int a[62][62];
	matrix operator *(const matrix b) const {
		matrix res;
		res.n=n;res.m=b.m;
		for(int i=1;i<=n;i++) for(int j=1;j<=b.m;j++) res.a[i][j]=0;
		for(int i=1;i<=m;i++) {
			for(int j=1;j<=n;j++) {
				for(int k=1;k<=b.m;k++) (res.a[j][k]+=a[j][i]*b.a[i][k]%mod)%=mod;
			}
		}
		return res;
	}
}A,B,C;
struct node{int a[3];
	bool operator <(const node &b) const {
		if(a[0]!=b.a[0]) return a[0]<b.a[0];
		if(a[1]!=b.a[1]) return a[1]<b.a[1];
		return a[2]<b.a[2];
	}
};
queue<set<node>> q;
set<node> o;
map<set<node>,int> mp;
int f[5]={0,4,10,4},cnt,cnt2;
inline int modify(int a,int b) {
	if(a==0) return 0;
	if(a==2) return 1;
	if(a==8) return 2;
	if(a==4&&b==1) return 3;
	if(a==4&&b==3) return 4;
	return -1;
}
vector<int> g,gg;
inline void matrix_quickpow(matrix &res,matrix a,int b) {
	while(b) {
		if(b&1) res=res*a;
		a=a*a;b>>=1;
	}
}
inline void solve3() {
	o.insert({0,0,0});q.push(o);mp[o]=++cnt;
	while(!q.empty()) {
		set<node> u=q.front();q.pop();
		for(node temp:u) if(!temp.a[0]&&!temp.a[1]&&!temp.a[2]) {g.push_back(mp[u]);break;}
		int b[3],c[3],d[3];
		for(b[0]=1;b[0]<=3;b[0]++) {
			for(b[1]=1;b[1]<=3;b[1]++) {
				for(b[2]=1;b[2]<=3;b[2]++) {
					set<node> curr;curr.clear();
					for(node temp:u) {
						c[0]=c[1]=c[2]=-1;
						d[0]=f[b[0]],d[1]=f[b[1]],d[2]=f[b[2]];
						bool flag=1;
						for(int i=0;i<=2;i++) {
							if(temp.a[i]==1||temp.a[i]==2) c[i]=0,d[i]^=4;
							if(temp.a[i]==3) c[i]=2,d[i]^=2;
							if(temp.a[i]==4) c[i]=1,d[i]^=8;
							if(temp.a[i]==1&&b[i]!=1) flag=0;
							if(temp.a[i]==2&&b[i]!=3) flag=0;
							if(temp.a[i]==3&&b[i]!=2) flag=0;
							if(temp.a[i]==4&&b[i]!=2) flag=0;
						}
						if(!flag) continue;
						
						if(c[0]!=-1&&c[1]!=-1&&c[2]!=-1) {curr.insert({c[0],c[1],c[2]});continue;}
						//0与1连边
						if(((d[0]>>b[1])&1)&&((d[1]>>b[0])&1)) {
							d[0]-=(1<<b[1]);
							d[1]-=(1<<b[0]);
							if(((d[2]>>b[1])&1)&&((d[1]>>b[2])&1)) {
								d[2]-=(1<<b[1]);
								d[1]-=(1<<b[2]);
								//1与2连边
								for(int i=0;i<3;i++) c[i]=modify(d[i],b[i]);
								curr.insert({c[0],c[1],c[2]});
								d[2]+=(1<<b[1]);
								d[1]+=(1<<b[2]);
							}
							//1与2不连边
							bool x=0;
							for(int i=0;i<3;i++) {c[i]=modify(d[i],b[i]);if(c[i]==-1) x=1;}
							if(!x) curr.insert({c[0],c[1],c[2]});
							d[0]+=(1<<b[1]);
							d[1]+=(1<<b[0]);
						}
						//0与1不连边
						if(((d[2]>>b[1])&1)&&((d[1]>>b[2])&1)) {
							d[2]-=(1<<b[1]);
							d[1]-=(1<<b[2]);
							//1与2连边
							bool x=0;
							for(int i=0;i<3;i++) {c[i]=modify(d[i],b[i]);if(c[i]==-1) x=1;}
							if(!x) curr.insert({c[0],c[1],c[2]});
							d[2]+=(1<<b[1]);
							d[1]+=(1<<b[2]);
						}
						//1与2不连边
						bool x=0;
						for(int i=0;i<3;i++) {c[i]=modify(d[i],b[i]);if(c[i]==-1) x=1;}
						if(!x) curr.insert({c[0],c[1],c[2]});
					}
					if(curr.empty()) {continue;}
					if(mp[curr]) {
						A.a[mp[u]][mp[curr]]++;
						continue;
					}
					A.a[mp[u]][cnt+1]++;
					mp[curr]=++cnt;
					q.push(curr);
				}
			}
		}
	}
	A.n=A.m=cnt;
}
inline void solve2() {
	o.insert({0,0,0});q.push(o);mp[o]=++cnt2;
	while(!q.empty()) {
		set<node> u=q.front();q.pop();
		for(node temp:u) {if(temp.a[0]==0&&temp.a[1]==0) {gg.push_back(mp[u]);break;}}
		int b[3],c[3],d[3];
		for(b[0]=1;b[0]<=3;b[0]++) {
			for(b[1]=1;b[1]<=3;b[1]++) {
				set<node> curr;curr.clear();
				for(node temp:u) {
					c[0]=c[1]=-1;
					d[0]=f[b[0]],d[1]=f[b[1]];
					bool flag=1;
					for(int i=0;i<=1;i++) {
						if(temp.a[i]==1||temp.a[i]==2) c[i]=0,d[i]^=4;
						if(temp.a[i]==3) c[i]=2,d[i]^=2;
						if(temp.a[i]==4) c[i]=1,d[i]^=8;
						if(temp.a[i]==1&&b[i]!=1) flag=0;
						if(temp.a[i]==2&&b[i]!=3) flag=0;
						if(temp.a[i]==3&&b[i]!=2) flag=0;
						if(temp.a[i]==4&&b[i]!=2) flag=0;
					}
					if(!flag) continue;
					if(c[0]!=-1&&c[1]!=-1) {curr.insert({c[0],c[1],0});continue;}
					//0与1连边
					if(((d[0]>>b[1])&1)&&((d[1]>>b[0])&1)) {
						d[0]-=(1<<b[1]);
						d[1]-=(1<<b[0]);
						bool x=0;
						for(int i=0;i<2;i++) {c[i]=modify(d[i],b[i]);if(c[i]==-1) x=1;}
						if(!x) curr.insert({c[0],c[1],0});
						d[0]+=(1<<b[1]);
						d[1]+=(1<<b[0]);
					}
					//0与1不连边
					bool x=0;
					for(int i=0;i<2;i++) {c[i]=modify(d[i],b[i]);if(c[i]==-1) x=1;}
					if(!x) curr.insert({c[0],c[1],0});
				}
				if(curr.empty()) {continue;}
				if(mp[curr]) {
					C.a[mp[u]][mp[curr]]++;
					continue;
				}
				C.a[mp[u]][cnt2+1]++;
				mp[curr]=++cnt2;
				q.push(curr);
			}
		}
	}
	C.n=C.m=cnt2;
}
inline int quickpow(int a,int b) {
	int res=1;
	while(b) {
		if(b&1) (res*=a)%=mod;
		(a*=a)%=mod;b>>=1;
	}return res;
}
bool ed;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cerr<<(double)(&st-&ed)/1024/1024<<'\n';
	solve3();
	mp.clear();
	solve2();
	int t;cin>>t;
	while(t--) {
		int n,m;
		cin>>n>>m;
		if(n*m%3!=0) {cout<<0<<'\n';continue;}
		if(n==3) {
			memset(B.a,0,sizeof(B.a));
			B.n=1,B.m=cnt;B.a[1][1]=1;
			int res=0;
			matrix_quickpow(B,A,m);
			for(int i=0;i<g.size();i++) (res+=B.a[1][g[i]])%=mod;
			cout<<res<<'\n';
		}else if(n==1) {
			cout<<quickpow(2,m/3)<<'\n';
		}else {
			memset(B.a,0,sizeof(B.a));
			B.n=1,B.m=cnt2;B.a[1][1]=1;
			matrix_quickpow(B,C,m);
			int res=0;
			for(int i=0;i<gg.size();i++) (res+=B.a[1][gg[i]])%=mod;
			cout<<res<<'\n';
		}
	}
	return 0;
}