这道题好像题解是用了将dp数组差分然后什么什么的,我原来感觉做了没有什么用,因为这是真的不容易想到(差分这种想法还是可以记下的),然后某天菜菜问了我这道题,我看了栋栋的题解,发现了好的做法。


我们知道每个排列与笛卡尔树一一对应。
然后就可以考虑这个排列的笛卡尔树。
我们考虑按权值从小到大依次加点:
在任何时刻,当前维护的排列的笛卡尔树一定是一个森林,其中每棵树,代表着一段。

那么新加入一个点时很显然有这三种操作

  • 当前这个点和一段合并
  • 当前这个点和两段合并
  • 当前这个点单独成段

要注意的是,我们要将这些段分为三类:与S联通的,与T联通的,与S和T都不联通的,必须保证S和T在在加入最后一个点时联通,任何时候T所在树必须接在父亲的右儿子,S所在联通块只能成为父亲的左儿子。

然后我们如何保证这个序列是以上一下的呢,我们可以注意到,要想成功地与父亲节点相连,(除了S所在的树)每个点的开头必须是递增,(除了T所在的树)结尾必须是递减

然后我们就可以dp了,我们对于s开头是递增还是递减分别算就行,(因为根据n的奇偶性,t结尾的增减性是可以得出的)

我们只考虑递增的情况,f[i][j]表示已加入i个点,有j个段的方案数。

  • i != s && i != t时

定义k=(s<=i)+(t<=i)
$$
\left\{\begin{matrix}
f[i+1][j+1] \leftarrow f[i][j] \\
// f[i+1][j] \leftarrow f[i][j]*(2*j-k) (Error!!)\\
f[i+1][j-1] \leftarrow f[i][j]*(j-k)*(j-1)/2
\end{matrix}\right.
$$
注意一下中间的那个转移是不能用的

  • i == s || i == t 时

同上面,讨论一下即可!
这道题就OK了

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
#include<bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, N = 2005;
int n, s, t, f[N][N];
void up (int &x, int y) { x += y; if (x >= P) x -= P; }
int Solve (int s, int t) {
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 0, k; i < n - 1; ++i) {
for (int j = 0; j <= i; ++j) if (f[i][j]) {
if (i + 1 == s) {
up(f[i + 1][j + 1], f[i][j]);
} else if (i + 1 == t) {
if (n & 1) up(f[i + 1][j + 1], f[i][j]); // n为奇, 最后一对数递减
else up(f[i + 1][j], 1ll * f[i][j] * (j - (s <= i)) % P); // 递增
} else {
k = (s <= i) + (t <= i);
up(f[i + 1][j + 1], f[i][j]);
// up(f[i + 1][j], 1ll * f[i][j] * (2 * j - k) % P);
up(f[i + 1][j - 1], 1ll * (j - k) * (j - 1) % P * f[i][j] % P);
}
}
}
return f[n - 1][2 - (s == n || t == n)];
}
int main () {
scanf("%d%d%d", &n, &s, &t);
if (n == 1) return puts("1"), 0;
if (s == t) return puts("0"), 0;
int ans = Solve(s, t);
ans = (ans + Solve(n - s + 1, n - t + 1)) % P;
if (ans < 0) ans += P;
printf("%d\n", ans);
return 0;
}