简要题意
略
思路
先考虑啥样的 \(T\) 可能合法，就大概类似于一个一边删除，一边加入的操作，如果能删空，那就合法
但这样的 \(T\) ，不一定能作为答案，只有能将多余的数删除时才合法
那就用同样的策略，判断是否合法即可
接着考虑 \(T\) 的方案数咋求，设 \(dp_{i,j,k}\) ，表示从大到小填到数字 \(i\)，\(0 \sim i-1\)共填了 \(j\) 次，后面可以多贡献 \(k\) 个 \(0\)，暴力转移，复杂度 \(O(n^2mlogm)\)
code
#include<bits/stdc++.h>
using namespace std;
#define N 105
int zu,n,ans,m,x;
int f[N][N][N],g[N][N],u[N];
const int mod=998244353;
void mo(int &x){
if(x>=mod) x-=mod;
}
int chk(int num,int cnt){
int xu=1,sum=0;
for(int j=num-1;j>=1;j--){
if(u[j]>=xu) cnt+=u[j]-xu;
else xu+=xu-u[j];
sum+=u[j];
xu=min(xu,n+2);
}
if(!sum&&u[0]+cnt==0) return 1;
if(u[0]+cnt+1>=xu) return 1;
return 0;
}
int main(){
freopen("normal.in","r",stdin);
freopen("normal.out","w",stdout);
scanf("%d",&zu);
while(zu--){
scanf("%d",&n);
m=ans=0;
memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(u,0,sizeof(u));
for(int i=1;i<=n;i++) scanf("%d",&x),u[x]++;
m=100;
f[m+1][0][0]=1;
for(int i=m;i>=1;i--){
for(int j=0;j<=n;j++){
for(int k=0;k<=n;k++){
if(!f[i+1][j][k]) continue;
for(int p=j;p<=n;p++){
if(p<=u[i]){
f[i][j][k+u[i]-p]+=f[i+1][j][k],mo(f[i][j][k+u[i]-p]);
if(!j&&p>0) g[i][k+u[i]-p]+=f[i+1][j][k],mo(g[i][k+u[i]-p]);
}
else if(j+p-u[i]<=n) f[i][j+p-u[i]][k]+=f[i+1][j][k],mo(f[i][j+p-u[i]][k]);
}
}
}
}
for(int j=0;j<=n;j++){//add:0
for(int k=0;k<=n;k++){
if(!f[1][j][k]) continue;
for(int p=max(j,1);p<=n;p++){
if(p<=u[0]+k) ans+=f[1][j][k],mo(ans);
}
}
}
for(int i=1;i<=m;i++){
for(int k=0;k<=n;k++){
if(!g[i][k]) continue;
if(chk(i,k)) ans+=g[i][k],mo(ans);
}
}
printf("%d\n",ans);
}
return 0;
}