LINK
Problem Description There are N blanks arranged in a row. The blanks are numbered 1,2,…,N from left to right. Tom is filling each blank with one number in {0,1,2,3}. According to his thought, the following M conditions must all be satisfied. The ith condition is: There are exactly xi different numbers among blanks ∈[li,ri]. In how many ways can the blanks be filled to satisfy all the conditions? Find the answer modulo 998244353.
Input The first line of the input contains an integer T(1≤T≤15), denoting the number of test cases. In each test case, there are two integers n(1≤n≤100) and m(0≤m≤100) in the first line, denoting the number of blanks and the number of conditions. For the following m lines, each line contains three integers l,r and x, denoting a condition(1≤l≤r≤n, 1≤x≤4).
Output For each testcase, output a single line containing an integer, denoting the number of ways to paint the blanks satisfying all the conditions modulo 998244353.
Sample Input
2 1 0 4 1 1 3 3
Sample Output
4 96
这道题针对的是对一个区间内不同数的个数的要求而对具体的数字没有要求 —>神奇的DP dp[p][j][k][h] 表示有四个不同的数 他们的最后一个数所在的位置分别是 p,j,k,h（p>=j>=k>=h 等号针对的位置就是都在0 的位置比如对于 样例1 0 那么就是第一位随便取（1,2,3,4） 取 1 在第一位的话那么2 3 4 就都在0 位了） 采用滚动数组优化空间
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; ll dp[2][110][110][110]; int main() { int tt;scanf("%d",&tt); while(tt--) { int n,m;scanf("%d%d",&n,&m); vector<pair<int,int>>v[110]; for(int i=1;i<=m;i++) { int a,b,x;scanf("%d%d%d",&a,&b,&x); v[b].push_back(pair<int,int>(a,x)); } for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { for(int h=0;h<=j;h++) dp[0][i][j][h]=dp[1][i][j][h]=0; } } dp[0][0][0][0]=1ll; for(int i=1,p=1;i<=n;i++,p^=1) { for(int j=0;j<i;j++) { for(int k=0;k<max(j,1);k++) { for(int h=0;h<max(k,1);h++) dp[p][j][k][h]=0ll; } } for(int j=0;j<i;j++) { for(int k=0;k<max(j,1);k++) { for(int h=0;h<max(k,1);h++) { (dp[p][j][k][h]+=dp[p^1][j][k][h])%=mod; //i出现的数是出现在i-1的数 (dp[p][i-1][k][h]+=dp[p^1][j][k][h])%=mod; //i位置上的数是上次出现在j位置上的数 (dp[p][i-1][j][h]+=dp[p^1][j][k][h])%=mod; //i位置上的数是上次出现在k位置上的数 (dp[p][i-1][j][k]+=dp[p^1][j][k][h])%=mod; //i位置上的数是上次出现在h位置上的数 } } } for(int j=0;j<i;j++) { for(int k=0;k<max(j,1);k++) { for(int h=0;h<max(k,1);h++) { for(int q=0;q<v[i].size();q++) { if(1+(j>=v[i][q].first)+(k>=v[i][q].first)+(h>=v[i][q].first)!=v[i][q].second)// 判断是否符合要求 { dp[p][j][k][h]=0;// 不符合要求就清零 } } } } } } ll ans=0; for(int j=0,p=n&1;j<n;j++) { for(int k=0;k<max(j,1);k++) { for(int h=0;h<max(k,1);h++) { (ans+=dp[p][j][k][h])%=mod; } } } printf("%lld\n",ans); } }