我们设 \(f[i][j][k]\) 表示填到 \(i\) 个数，目前拓展出 \(j\) 个可以填数的区间（最两边不算，注意是可以填数的区间！！），贡献和为 \(k\) 。
这个是可以填数的区间
我们按从小到大进行填数。
那么对于任意一个数x显然有三种情况。
1.如果x左右目前都没数，那么说明它的左右两个数都比x大，此时x的贡献为0.
2.如果x左右有一个数，那么它的贡献为x。
3.如果x左右都有数，那么它的贡献为\(2*x\)。
那我们根据这些来设计状态转移方程。
1.如果填数位置在我们已经拓展的总区间的左右边界外：
如果旁边还没填，那它就能拓展出一个可以填数的区间,左右都能拓展要乘二，但并不会增加贡献。\(f[i][j+1][k]+=f[i-1][j][k]*2\)
如果旁边已经填了，即就在左右边界旁边，则会提供 \(i\) 的贡献，区间并不拓展。\(f[i][j][k+i]+=f[i-1][j][k]*2\)
2.如果填数位置在区间内部，那它会有三种情况，一是两边都没数，二是只有一边有数，三是两边都有数，我们逐个分析：
先说第一种情况：两边都没数，那它会拓展出一个中间可填数的区间，目前有 \(j\) 个可以填数的区间，所以乘 \(j\) ，不会提供贡献。\(f[i][j+1][k]+=f[i-1][j][k]*j\)
然后是只有一边有数的情况，它会提供 \(i\) 的贡献，共有 \(j\) 个可以填数的区间，每个区间有两个已经填数的边界，所以乘 \(j*2\) ，不会拓展出区间。\(f[i][j][k+i]+=f[i-1][j][k]*j*2\)
最后一种，两边都有数，我们就同样去考虑，它首先会提供 \(2*i\) 的贡献，并且会合并两个区间，所以区间会减 \(1\) ,有 \(j\) 个可以填数的区间，所以乘 \(j\) 。\(f[i][j-1][k+2*i]+=f[i-1][j][k]*j\)
到这里，我们的分析就完成了（太不容易了）。
关于预设型DP的的感想：刚接触时，这是什么东西，还能这样设计状态，这正确性真对吗？后来仔细想了想，我个人理解是，有一些无法构成正确区间的状态在转移的时候就已经被舍去了，使一些不合法的解被排除。同时，我们的区间构造是动态的，并没有明确的左右边界。正是这些条件使得预设型DP的正确性可以得到保证。
using namespace std;
#define int long long
const int N=60;
const int mod=998244353;
int n,m,ans;
int f[N][N][2540];
signed main()
{
scanf("%lld%lld",&n,&m);
f[1][0][0]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=n-i+1;j++)
{
for(int k=0;k<=m;k++)
{
f[i][j+1][k]=(f[i][j+1][k]+f[i-1][j][k]*2)%mod;
f[i][j][k+i]=(f[i][j][k+i]+f[i-1][j][k]*2)%mod;
if(j!=0)
{
f[i][j+1][k]=(f[i][j+1][k]+f[i-1][j][k]*j)%mod;
f[i][j][k+i]=(f[i][j][k+i]+f[i-1][j][k]*j*2)%mod;
f[i][j-1][k+i*2]=(f[i][j-1][k+i*2]+f[i-1][j][k]*j)%mod;
}
}
}
}
for(int i=0;i<=m;i++)
{
ans=(ans+f[n][0][i])%mod;
}
printf("%lld",ans);
}`