序

    题意大概是，给出t组询问，每组第一行给出两个数n和m，n是数列长度，m是要求，接下来m行，每行包括三个数l，r，x，要求在l~r区间内有x种不同数字，整个数列由0，1，2，3组成，求满足条件的排列方式。

    这题一看就感觉要DP，然鹅想了很久也不知道怎么DP，期间也想过可以记录四种数字的位置，但是根本想不出怎么转移，甚至看了别人博客也没明白（大佬只放了代码，看不懂，哭唧唧）。结果搞了半下午，才弄明白思路。

    此题的关键在于其状态转移方程转移的方式有点与众不同，对我来说在拿到ac代码后甚至也看不大明白，假如纯靠自己去推那必然是极难的，理解转移方程需要能想到一点特殊的转移方式，还需要灵光一现。

基本思路

    首先，我们应该很容易想到用四个字母来分别标记每种数字最后一次出现的位置，一般类似于这样构造符合某种条件的序列的题，都会这样标记吧，以题解为例，分别以p，j，k，t来标记四种数字的位置。但是假如规定了四个字母分别对应什么数字，这样的话转移过程中的时间复杂度会变得很高，因为需要考虑到所有情况，所以是一个满的N4，但事实上里面有很多重复和冗余，而题解中所采用的方法，并没有具体规定四个字母所对应的数字，而是规定，也就是说，每个字母表示什么数字，取决于每个数字最后一次出现时的相对位置，这样的好处是，应该是能省一点时间，还有就是写起来会方便一些，前面那种有兴趣可以自行体会一下繁琐程度。

    那么，状态要如何转移呢？我们先不去考虑题目中的m个要求（毕竟理解了标程之后突然感觉到这些要求就好像买一赠一的赠品一样，只要状态转移方程推出了就一切ok），假如现在四个字母p，j，k，t表示四个数字最后出现的位置，那么它的后继状态有四个，分别是当前在p，j，k，t位置上的数字添加到当前数列的后面，于是有如下四种结果（设下一位为第i位）：

    dp[i][j][k][t]    p位置的数字加到数列最后 dp[i][p][k][t]    j位置的数字加到数列最后

    dp[i][p][j][t]    k位置的数字加到数列最后 dp[i][p][j][k] t位置的数字加到数列最后

    当然，这里还存在一个小问题，那就是数组开不下，所以我们需要使用滚动数组来记录每一步的结果，这里把状态转移方程改变一下，用p来标记，例如可以使p只等于0或1，来标记当前走到了哪步，所以只需要每次只记录相邻两步，一直更新到最后即可。此举可节省空间复杂度，当然循环该怎么写还是怎么写，我们这里用i来标记当前末尾的位置：

    dp[p][j][k][t]    i位置的数字加到数列最后，其他三个数位置不变

    dp[p][i-1][k][t]    j位置的数字加到数列最后即第i位，i-1即上一步末尾的数字，下同

    dp[p][i-1][j][t]    k位置的数字加到数列最后

    dp[p][i-1][j][k] t位置的数字加到数列最后

    接下来，我们就可以开始愉快地写代码了，只需要在递推的过程中，每步判断当前状态符不符合每个条件，符合则保留，不符合则置0，然后就可以开心地ac了。

    （虽然我的代码和标程高度相似，但这真的是自己写的！！！（看了标程之后233））
 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
const ll N=110;
ll n,m,ans,t,l,r,x;
ll dp[2][N][N][N];//dp数组
const ll mod=998244353;
vector<pair<int,int>> ve[N];//存m个条件
int main(){
    scanf("%lld",&t);
    while(t--){
        ans=0;
        scanf("%lld %lld",&n,&m);
        for(int i=1;i<=n;i++)
            ve[i].clear();//初始化vector
        for(int i=0;i<m;i++){
            scanf("%lld %lld %lld",&l,&r,&x);
            ve[r].push_back(pair<int,int>(l,x));//l，r区间内有x种数字，由于递推过程中循环中的i是数列末位，
                                                            //所以这里记录右边界，方便一会判断
        }
        dp[0][0][0][0]=1;//啥都没有的情况，当然只有一种
        for(int i=1,p=1;i<=n;i++,p^=1){//p每次异或，以0和1来标记
            //初始化本层的数组
            for(int j=0;j<=i;j++)
                for(int k=0;k<=j;k++)
                    for(int t=0;t<=k;t++)
                        dp[p][j][k][t]=0;
            //这部分的状态转移方程应该已经讲得很清楚了，别忘了取模
            for(int j=0;j<i;j++)
                for(int k=0;k<=j;k++)
                    for(int t=0;t<=k;t++){
                        (dp[p][j][k][t]+=dp[p^1][j][k][t])%=mod;
                        (dp[p][i-1][k][t]+=dp[p^1][j][k][t])%=mod;
                        (dp[p][i-1][j][t]+=dp[p^1][j][k][t])%=mod;
                        (dp[p][i-1][j][k]+=dp[p^1][j][k][t])%=mod;
                    }
            //对于本层每个状态，判断是否符合条件，因为右边界固定在当前状态的末位，只需要判断每个数最后出现的位置是否在左边界之后，
                        //即可知道共有几种数
            for(int j=0;j<i;j++)
                for(int k=0;k<=j;k++)
                    for(int t=0;t<=k;t++)
                        for(int pi=0;pi<ve[i].size();pi++)
                            if(1+(j>=ve[i][pi].first)+(k>=ve[i][pi].first)+(t>=ve[i][pi].first)!=ve[i][pi].second)
                                dp[p][j][k][t]=0;//不满足条件，置0
        }
        //把最后一层的答案加起来就好
        for(int i=0,p=n&1;i<n;i++)
            for(int j=0;j<=i;j++)
                for(int k=0;k<=j;k++)
                    (ans+=dp[p][i][j][k])%=mod;
        printf("%lld\n",ans);
    }
}