题意：现在要你构造一个只有{0，1，2，3} 长度为n且有m个限制条件的序列 问你方案数
思路：dp[i][j][k][now]分别表示四个数最后出现的位置 最后可以滚动数组 优化一下空间
ps：我的代码常数很大 其实有很多可以优化的地方
#include <bits/stdc++.h> 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<pair<int,int> > 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 ",ans); } }