DP搬运工1

Description

给你 n,k，求有多少个 1 到 n 的排列，满足相邻两个数的 max 的和不超过 k。

Input Format

一行两个整数 n,k。

Output Format

一行一个整数 ansans 表示答案 \(\text{mod 998244353}\)。

Sample

样例输入1
4 10
样例输出1
16
样例输入2
10 66
样例输出2
1983744

Hint

有 50 个 测试点，第 i 个测试点为 n=i ， \(k\leq n^2\) 。

题解

对于此题我们很难设计状态，其中最难是得保证每个数只选了一次，因此我们不能枚举每一位该填什么,而是这个数填哪个位置
由于本题性质，可以从小到大枚举方便算其贡献；

然而依旧不是那么好做，需要设计一个恰当的状态。其实预设型DP还有另外的一个名字连续段DP，我们可以设 $$f_{i,j,k}表示枚举到第 i 个数，所填位置中间有 j 个断点时总贡献为 k 的个数$$
其中 j 这一维略显突兀，用图形表示填法大致如下：

连续的O表示连续填的数，()表示中间有一个断点，这个时候的j就表示有几个()，不考虑两端
我们并不会考虑()中间有多少个空位，只需知道有这么个空位就行了这就足够给出转移方程了：

分类讨论：

• 一.放两边扩充
  1. 紧贴两边新增贡献为 i ，有两边所以计数乘 2 ：
     \(f[i][j][k+i]+=f[i-1][j][k]*2\)
  2. 隔开填没有新贡献，但是会增加一个断断点，有两边所以计数乘 2 ：
     \(f[i][j+1][k]+=f[i-1][j][k]*2\)
• 二.在中间断点部分进行操作
  1. 紧贴断点两侧的连续段新增贡献为 i ，有 j 个断点 每个断点两边分别计数 所以计数乘 j*2 ：
     \(f[i][j][k+i]+=f[i-1][j][k]*j*2\)
  2. 在断点中间填没有新增贡献，但会增加断点数，有 j 个断点所以计数乘 j ：
     \(f[i][j+1][k]+=f[i-1][j][k]*j\)
  3. 减少一个断点，即把断点两边的连续段用我们新填的数连起来，此时贡献为 i*2，断点减少 1 ，有 j 个断点所以计数乘 j ：
     \(f[i][j-1][k+2*i]+=f[i-1][j][k]*j\)

初始状态 \(f_{1,0,0}=1\)
答案 \(\displaystyle \sum^{k}_{i=1} {f_{n,0,i}}\)

这个DP设计并没有考虑中间断点的距离为多长，可以想做每个断点的距离实际上有无限长。
操作二.3 是强行把一个断点两边的连续段连在一起，考虑也只是相对位置，并不是有些题解中写的每次状态转移会筛掉一部分不合法状态的计数，或是在答案中无法体现，它都是合法的。
不要拘束于它只有 n 个可填位置，用相对位置去理解，到最后填完的时候自然就没有断点了，也正好填了那么多位。

const int mod=998244353;
ll f[52][52][2610];

inline void m(ll &x,const ll &y)
{
	x=(x+y)%mod;
}

signed main()
{
	int n=read(),k=read();
	
	f[1][0][0]=1;
	for(int i=2;i<=n;++i)
		for(int j=0;j<=n;++j)
			for(int u=0;u<=k;++u)
			{
				//两边 
				m(f[i][j][u+i],f[i-1][j][u]*2);//贴边
				m(f[i][j+1][u],f[i-1][j][u]*2);//空
				
				//中间
				m(f[i][j][u+i],f[i-1][j][u]*j*2);//贴边
				m(f[i][j+1][u],f[i-1][j][u]*j);//中间
				if(j)m(f[i][j-1][u+2*i],f[i-1][j][u]*j);//连接 
			}
	
	ll ans=0;	
	for(int i=0;i<=k;++i)
		m(ans,f[n][0][i]);
		
	__print(ans);
	
	return 0;
}