这题让我没什么头绪。想到过使用前缀和来转换，但 的变化量看上去非常难以处理。最后发现是一个从未见过的 DP 模型，果然 ARC 题还是有学习价值的（前提是找得到好题）。

题意：计数满足下列条件的长度为 的序列 ：

1. 恰好包含 个 和 个 。
2. 恰好有 对 满足

。

求出 的前缀和 ，设 表示有多少个 等于 ，那么上述条件等价于：。

另一方面，。

注意到这个 的约束是关于每种值独立的，我们尝试设计关于值的 DP。

要把值的限制和相差 的限制统一起来，我们尝试 DP 这个序列 S 的笛卡尔树。

如下图：

我们在这个笛卡尔树上，从上到下，一层一层的 DP,每次填完一层的所有数。

设 表示一共填了 个数，已经填的数在 序列上形成 个连续段，一共填了 层，当前的 的方案数。

考虑最后怎么求答案，因为最后强制 ，我们考虑把 和 的部分拼接起来。

注意到这两种情况是对称的，我们都可以用这个 DP 状态来表示。

设 。

具体地，因为拼的时候肯定是一段 和一段 交错，那么我们枚举 的个数 ，段数 ，这一部分的 ，那么最后的答案就是 进一步地，我们发现 DP 中的 是没用的，可以去掉。

我们考虑新一层加入了 个数的影响。

会出现一下三种情况：

1. 某两段之间的间隙被连接，需要占用一个位置，并把两个段合并成一个
2. 某个段间隙没有被连接，因为 的变化连续，必须在这个间隙的两段贴两个数来拓展
3. 加入一个新的“山谷”

重点在于考虑段数的变化。

当前有 个连续段，就有 个空隙，每个空隙中都必须填数（因为我们是从上到下来填的数，每次填的是当前序列中的最小值，而我们限制了序列两端是 ，所以两端的空隙也必须填数；另一方面，因为 的变化是连续的，所以中间的空隙不填数就不合法了）

由上面三种情况整合可得，在单一个中间空隙中填入了 个数，会给总段数带来 的变化量。两端则是 。

整理式子可得新的连续段数为 。

考虑转移系数，相当于在 个盒子里放 个球，每个盒子都不为空，插板可得系数为

综上所述，有转移 。

#include <bits/stdc++.h>
using namespace std;
const int N = 65;
typedef long long ll;
int n,k;
ll C[N][N];
ll dp[N][N][N * N];
int main()
{
	cin >> n >> k;
	C[0][0] = 1;
	for(int i = 1;i <= n + 1;i++)
	{
		C[i][0] = C[i][i] = 1;
		for(int j = 1;j < i;j++)
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
	}
	for(int x = 0;x <= n + 1;x++)
		if(x * (x - 1) / 2 <= k)
			dp[x][x][x * (x - 1) / 2] = 1;
	for(int i = 1;i <= 2 * n + 1;i++)
		for(int c = 0;c <= k;c++)
			for(int j = 1;j <= min(n + 1,i);j++)
			{
				ll val = dp[i][j][c];
				if(val)
				{
					for(int x = j + 1;x <= n + 1;x++)
					{
						int nxt_c = c + x * (x - 1) / 2;
						if(i + x > 2 * n + 1 || nxt_c > k) continue;
						dp[i + x][x - j][nxt_c] += C[x - 1][j] * val;
					}
				}
			}
	ll ans = 0;
	for(int i = 0;i <= 2 * n + 1;i++)
		for(int j = 1;j <= n + 1;j++)
			for(int c = 0;c <= k;c++)
				ans += dp[i][j][c] * dp[2 * n + 1 - i][j - 1][k - c];
	cout << ans << endl;
	return 0;
}