Problem Link

考虑依次插入 $p_1\sim p_n$，如何满足一个 $T$ 中排列 $t$ 的限制，显然任意 $p[1,i]$ 在 $t$ 中都形如一个前缀加一个区间，维护该结构即可完成判定。

那么朴素想法就是 $f_{i,k,j}$ 表示当前填入的 $p$ 前缀为 $t_1[1,i]+t_1[k,j]$，每次枚举加入 $t_{1,i+1}$ 或 $t_{1,j+1}$。

但一个问题是判定时如果当前 $p$ 的前缀在某个 $t_x$ 中形成了一个前缀，那么我们无法判断这个结构是原始的一个前缀，还是连起来的前缀 $+$ 区间。

所以我们的目标就是确定每个 $t$ 区间的起点再 dp。

首先枚举 $p_1$，若 $t_1\ne p_1$ 则区间起点就是 $t_1$，然后进一步枚举 $p_2,p_3,\dots$ 直到所有 $t$ 的区间起点被确定，可以证明这个过程只会搜到 $\mathcal O(n^2+nm)$ 种前缀。

具体来说考虑加入一个 $p_i$ 后所有区间起点被确定，那么如果在 $p[1,i-1]$ 已经有 $t_x$ 的区间起点被确定，则此时的 $p_i$ 被 $t_x$ 限定成至多两种取值，而这种前缀的总数是 $\mathcal O(nm)$ 级别。如果 $p[1,i-1]$ 处没有任何区间起点被确定，这种前缀总数 $\mathcal O(n)$，因此总的前缀种数为 $\mathcal O(n^2+nm)$。

那么我们在这个基础上 dp，$f_{i,k,j}$ 含义不变，由于所有区间起点被确定，判断转移合法性时只要看加入的这个字符的前一个字符是否被加入，容易优化到 $\mathcal O(1)$ 判定。

时间复杂度 $\mathcal O(n^3+n^2m)$

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=305,MOD=998244353;
basic_string <array<int,2>> dp[MAXN];
int n,m,a[MAXN][MAXN],p[MAXN][MAXN],f[MAXN][MAXN],ans;
int s[MAXN],t[MAXN];
bool vis[MAXN];
void dfs(int k) {
	if(k==n) return ans=(ans+1)%MOD,void();
	if(!count(t+1,t+m+1,0)) return dp[t[1]].push_back({s[1],t[1]+k-s[1]-1});
	vector <int> w;
	for(int i=1;i<=n;++i) if(!vis[i]) w.push_back(i);
	for(int i=1;i<=m;++i) if(t[i]) {
		vector <int> o;
		for(int v:w) if(v==a[i][s[i]+1]||v==a[i][t[i]+k-s[i]]) o.push_back(v);
		w.swap(o);
	}
	for(int v:w) {
		for(int i=1;i<=m;++i) {
			if(v==a[i][s[i]+1]) ++s[i];
			else if(!t[i]) t[i]=p[i][v];
		}
		vis[v]=true,dfs(k+1),vis[v]=false;
		for(int i=1;i<=m;++i) {
			if(v==a[i][s[i]]) --s[i];
			else if(t[i]==p[i][v]) t[i]=0;
		}
	}
}
int g[MAXN][MAXN];
bool chk(int i,int k,int j,int c) { //[1,i]+[k,j]
	return g[c][i]+g[c][j]-g[c][k-1]==m-1;
}
int solve(int N,int M,vector<vector<int>>&S) {
	n=N,m=M;
	for(int i=1;i<=m;++i) for(int j=1;j<=n;++j) a[i][j]=S[i-1][j-1],p[i][a[i][j]]=j;
	dfs(0);
	for(int k=2;k<=n;++k) if(dp[k].size()) {
		memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
		for(auto i:dp[k]) ++f[i[0]][i[1]];
		for(int c=1;c<=n;++c) {
			for(int i=2;i<=m;++i) ++g[c][p[1][a[i][p[i][c]-1]]];
			for(int i=1;i<=n;++i) g[c][i]+=g[c][i-1];
		}
		for(int i=0;i<k;++i) for(int j=k;j<=n;++j) if(f[i][j]) {
			if(f[i][j]>=MOD) f[i][j]-=MOD;
			if(i<k-1&&chk(i,k,j,a[1][i+1])) f[i+1][j]+=f[i][j];
			if(j<n&&chk(i,k,j,a[1][j+1])) f[i][j+1]+=f[i][j];
		}
		ans=(ans+f[k-1][n])%MOD;
	}
	return ans;
}