这题让我没什么头绪。想到过使用前缀和来转换，但
的变化量看上去非常难以处理。最后发现是一个从未见过的 DP 模型，果然 ARC
题还是有学习价值的（前提是找得到好题）。
题意：计数满足下列条件的长度为 的序列 ：
- 恰好包含 个 和 个 。
- 恰好有 对 满足
。
求出 的前缀和 ，设 表示有多少个 等于 ，那么上述条件等价于：。
另一方面，。
注意到这个
的约束是关于每种值独立的，我们尝试设计关于值的 DP。
要把值的限制和相差
的限制统一起来，我们尝试 DP 这个序列 S 的笛卡尔树。
如下图：
我们在这个笛卡尔树上，从上到下，一层一层的
DP,每次填完一层的所有数。
设 表示一共填了
个数，已经填的数在 序列上形成 个连续段，一共填了 层，当前的 的方案数。
考虑最后怎么求答案，因为最后强制 ，我们考虑把 和
的部分拼接起来。
注意到这两种情况是对称的，我们都可以用这个 DP 状态来表示。
设 。
具体地，因为拼的时候肯定是一段 和一段
交错，那么我们枚举 的个数
，段数 ，这一部分的 ，那么最后的答案就是 进一步地，我们发现 DP 中的 是没用的，可以去掉。
我们考虑新一层加入了
个数的影响。
会出现一下三种情况：
- 某两段之间的间隙被连接，需要占用一个位置，并把两个段合并成一个
- 某个段间隙没有被连接，因为
的变化连续，必须在这个间隙的两段贴两个数来拓展
- 加入一个新的“山谷”
重点在于考虑段数的变化。
当前有 个连续段，就有
个空隙，每个空隙中都必须填数（因为我们是从上到下来填的数，每次填的是当前序列中的最小值，而我们限制了序列两端是
，所以两端的空隙也必须填数；另一方面，因为
的变化是连续的，所以中间的空隙不填数就不合法了）
由上面三种情况整合可得，在单一个中间空隙中填入了 个数，会给总段数带来 的变化量。两端则是 。
整理式子可得新的连续段数为 。
考虑转移系数，相当于在
个盒子里放
个球，每个盒子都不为空，插板可得系数为
综上所述，有转移 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #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;
}
|