题意：现在要你构造一个只有{0，1，2，3} 长度为n且有m个限制条件的序列 问你方案数

思路：dp[i][j][k][now]分别表示四个数最后出现的位置 最后可以滚动数组 优化一下空间

ps：我的代码常数很大 其实有很多可以优化的地方

#include
using namespace std;
const double pi = acos(-1.0);
const int N = 107;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
typedef long long ll;
const ll mod = 998244353;
inline int read(){
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} return x * f; } vector > v[N];
int dp[N][N][N][2];
bool check(int i,int j,int k,int now){
for(auto l:v[now]){
int tmp=l.first;
int x=(i>=tmp)+(j>=tmp)+(k>=tmp)+(now>=tmp);
if(x!=l.second){
return false;
}
}
return true;
}
int main(){
int t; t=read();
while(t--){
int n,m; n=read(); m=read();
for(int i=0;i<N;i++)
v[i].clear();
for(int i=1;i<=m;i++){
int l,r,x; l=read(); r=read(); x=read();
v[r].push_back(make_pair(l,x));
}
memset(dp,0,sizeof(dp));
dp[0][0][0][0]=1;
for(int now=1;now<=n;now++){
int o=(now&1);
for(int k=0;k<=now;k++)
for(int j=0;j<=k;j++)
for(int i=0;i<=j;i++){
dp[i][j][k][o]=0;
}
for(int k=0;k<=now;k++)
for(int j=0;j<=k;j++)
for(int i=0;i<=j;i++){
dp[i][j][now-1][o]=(dp[i][j][now-1][o]+dp[i][j][k][o^1])%mod;
dp[i][k][now-1][o]=(dp[i][k][now-1][o]+dp[i][j][k][o^1])%mod;
dp[j][k][now-1][o]=(dp[j][k][now-1][o]+dp[i][j][k][o^1])%mod;
dp[i][j][k][o]=(dp[i][j][k][o]+dp[i][j][k][o^1])%mod;
}
for(int k=0;k<=now;k++)
for(int j=0;j<=k;j++)
for(int i=0;i<=j;i++)
if(!check(i,j,k,now)){
dp[i][j][k][o]=0;
}
}
int ans=0;
for(int k=0;k<=n;k++)
for(int j=0;j<=k;j++)
for(int i=0;i<=j;i++)
ans=(ans+dp[i][j][k][n&1])%mod;
printf("%d\n",ans);
}
}