好题
先不考虑 \(b\) 序列的计数，我们先考虑构造 \(a\) 序列。
由于是区间 min，所以考虑从小到大填数（类似笛卡尔树），所以设 \(dp_{l,r,k}\) 表示在 \([l,r]\) 的区间中填的数都 \(\le k\)，那么就有了转移式 \(dp_{l,r,k} = \sum_{i} dp_{l,i-1,k-1} * dp_{i+1,r,k}\)
但是这个 dp 转移式仍然存在一定的问题，因为对于 \(b\) 序列有可能会算重，这个时候的处理也不难，让 \(i\) 每次跳到下一个 \(b\) 上面就行了。
然后我们发现 \(c\) 过大了，所以把 dp 式中最后一维 \(k\) 的表示填的数不超过第 \(k\) 大的数即可。
最后容斥一下统计答案即可。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define lowbit(x) x&(-x)
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
const int inf=1e9,N=105,mod=998244353;
int n,m,c;
int dp[N][N][N],mn[N],C[N][N];
struct node{int l,r;}p[N*N];
inline int Inv(int a,int b=mod-2){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
signed main(){
n=read(),m=read(),c=read();
for(int i=1;i<=m;i++) p[i].l=read(),p[i].r=read();
for(int i=1;i<=n+1;i++) for(int j=1;j<=min(n,c);j++) dp[i][i-1][j]=1;
C[0][0]=1;
for(int i=1;i<=N-5;i++){
C[i][0]=1;
for(int j=1;j<=N-5;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
for(int len=1;len<=n;len++){
for(int l=1;l+len-1<=n;l++){
int r=l+len-1;
for(int i=l;i<=r;i++) mn[i]=inf;
for(int i=1;i<=m;i++) if(l<=p[i].l&&p[i].r<=r) for(int j=p[i].l;j<=p[i].r;j++) mn[j]=min(p[i].r,mn[j]);
dp[l][r][1]=1;
for(int j=2;j<=min(n,c);j++) for(int i=l;i<=r;i++){
if(mn[i]==inf) continue;
(dp[l][r][j]+=dp[l][i-1][j-1]*dp[i+1][r][j])%=mod;
i=mn[i];
}
for(int j=1;j<=min(n,c);j++) (dp[l][r][j]+=dp[l][r][j-1])%=mod;
}
}
int p=1,ans=0;
for(int i=1;i<=min(n,c);i++){
p=p*(c-i+1)%mod*Inv(i)%mod;
int sum=0;
for(int j=i,w=1;j>=1;j--,w=-w) (sum+=w*dp[1][n][j]*C[i][j])%=mod;
(ans+=sum*p)%=mod;
}
cout<<(ans+mod)%mod<<'\n';
}