题目链接(CF洛谷) | 强烈推荐博客中观看。

这题是真的难想,我 cf 的题解看了好久才搞明白(我太菜了)。

题意

给你一个长度为 nn 的排列 aa,请你找出有多少个相同长度的排列 bbaa 相似。

如果对于所有区间 [l,r](1lrn)[l, r] (1 \le l \le r \le n),下面的条件满足:

MEX(al,al+1,,ar)=MEX(bl,bl+1,,br)\operatorname{MEX}(a_l, a_{l + 1}, \ldots , a_r) = \operatorname{MEX}(b_l, b_{l + 1}, \ldots , b_r)

我们就称排列 aabb 是相似的。

其中 MEX\operatorname{MEX} 对于数组 cc 的定义是:最小的,没有出现在 cc 中的非负整数 xx

例如 MEX([1,2,3,4,5])=0 MEX([0,1,2,4,5])=3\operatorname{MEX}([1,2,3,4,5]) = 0 \ \operatorname{MEX}([0,1,2,4,5]) = 3

由于答案可能会很大,所以输出时需要打印答案模 109+710^9 + 7 的结果。

思路

直接想答案可能比较难,可以先模拟一下给出的样例,尝试构造出一些 bb

a=[1,3,7,2,5,0,6,4]a = [1, 3, 7, 2, 5, 0, 6, 4]

我们从 00 这个数字开始考虑样例。可以发现在 bb 中,00 的位置一定和 aa 中的 00 的位置相等。

为什么呢?我们定义aa数字 ii 出现的位置为 posi\text{pos}_i,比如 pos0=6\text{pos}_0 = 6 (下标从 11 开始)。

这时,选择 [pos0,pos0][\text{pos}_0, \text{pos}_0] 的区间对比 aabbMEX\operatorname{MEX} 是否相等,首先,在 aa 中,因为 a[pos0]=0a[\text{pos}_0] = 0aaMEX([pos0])\operatorname{MEX}([\text{pos}_0]) 一定等于 11

如果 bb00 的位置被改变了,那么在 bb 中,因为 a[pos0]>0a[\text{pos}_0] > 0MEX([pos0])\operatorname{MEX}([\text{pos}_0]),就一定等于 00 了。

所以我们可以推断出 00 的位置是不能变的。

我们还能推出,11 的位置也是不能改变的。

可以考虑 [pos1(1),pos0(6)](1 3 7 2 5 0)[\text{pos}_1(1), \text{pos}_0(6)] (1\ 3\ 7\ 2\ 5\ 0)[pos1+1,pos0](3 7 2 5 0)[\text{pos}_1 + 1, \text{pos}_0](3\ 7\ 2\ 5\ 0) 这两个区间的 MEX\operatorname{MEX} 值。

因为 11 的存在, MEX([pos1,pos0])\operatorname{MEX}([\text{pos}_1, \text{pos}_0]) 一定大于 11,而因为有 00 并且没有 11 MEX([pos1+1,pos0])\operatorname{MEX}([\text{pos}_1 + 1, \text{pos}_0]) 一定等于 11

架设我们在 bb 中改变了 11 的位置,比如改到了 22,那么在 bb 中, MEX([pos1+1,pos0](1 7 2 5 0))\operatorname{MEX}([\text{pos}_1 + 1, \text{pos}_0](1\ 7\ 2\ 5\ 0)) 就大于 11 了,不符合 aa 中等于 11 的情况。


现在考虑能合法放置 22 的位置。我们可以推断出,如果在 aa2(pos1,pos0)2 \in (\text{pos}_1, \text{pos}_0),那么在 bb 中, 22 就可以被放在 (pos1,pos0)(\text{pos}_1, \text{pos}_0) 这个区间的任意位置。

为啥呢?我们设区间 [l,r][l, r]aa 中包含 0011,也就是 lpos1,pos0rl \le \text{pos}_1, \text{pos}_0 \le r

那因为在 aa2(pos1,pos0)2 \in (\text{pos}_1, \text{pos}_0),a 中所有 [l,r][l, r]MEX\operatorname{MEX} 一定大于 22 (也就是说,在 aa 中,一个区间如果同时包含 0011,就一定会包含 22)。

同时,在 aa 中,不符合 lpos1,pos0rl \le \text{pos}_1, \text{pos}_0 \le r 的其他所有区间的 MEX\operatorname{MEX} 最大只有 11,(这样的区间最多包含一个 00,那么 MEX\operatorname{MEX} 就是 11 了)。

那么在 bb 中,只要 2(pos1,pos0)2 \in (\text{pos}_1, \text{pos}_0),就能符合 MEX([l,r])>2\operatorname{MEX}([l, r]) > 2。并且符合在不动其他数字的位置的情况下 aabb 相似。

符合这样的位置一共有 (pos0pos1+1)2(\text{pos}_0 - \text{pos}_1 + 1) - 2 个(2-2 是因为 0011 占用了区间内的两个位置)。


那么如果在 aa 中,2(pos1,pos0)2 \notin (\text{pos}_1, \text{pos}_0) 呢?

比如 a=[1,3,7,6,0,5,2,4]a = [1, 3, 7, 6, 0, 5, 2, 4]

我们可以推断出,和前面讲的 0011 一样,这种情况下,我们需要在 bb 中把 22 放到相同的位置上。

考虑 [pos1,pos2][\text{pos}_1, \text{pos}_2] 这个区间,其 MEX\operatorname{MEX} 一定大于 22。而 [pos1,pos21][\text{pos}_1, \text{pos}_2 - 1] 这个区间的 MEX\operatorname{MEX} 就一定等于 22(包含 0011)。

假设我们把 22 放到 pos21\text{pos}_2 - 1 上,那么 [pos1,pos21][\text{pos}_1, \text{pos}_2 - 1]MEX\operatorname{MEX} 就大于 22 了。

a=[1,3,7,6,5,0,2,4]a = [1, 3, 7, 6, 5, 0, 2, 4] 的情况下。

我们可以把 33 放在 (pos1,pos2)(\text{pos}_1, \text{pos}_2) 的区间内。因为只有这样,才能满足所有的 MEX[l,r]>3\operatorname{MEX}{[l, r]} > 3,其中,lpos0,pos1,pos2rl \le\text{pos}_0, \text{pos}_1, \text{pos}_2 \le r,并且除 [l,r][l, r] 之外的所有区间,MEX\operatorname{MEX} 都小于 33

也就是说,在 aa 中,如果一个区间包含了所有比 33 小的数,就一定会包含 33。或者说,在 aa 中,不可能会有一个区间的 MEX\operatorname{MEX} 等于 33,而为了满足这一点,我们需要让 3(pos1,pos2)3 \in (\text{pos}_1, \text{pos}_2)

我们设 xxmin[pos0pos3]\min{[\text{pos}_0 \ldots \text{pos}_3]}, yymax[pos0pos3]\max{[\text{pos}_0 \ldots \text{pos}_3]}。符合上面 3(pos1,pos2)3 \in (\text{pos}_1, \text{pos}_2) 条件的位置就有 (yx+1)3(y - x + 1) - 3 个(3-3 是因为区间中已经有 020 \sim 2 了)。


现在我们可以从刚刚的观察中推广一下。我们刚刚发现如果在 aa 中,一个数在所有比他小的数的中间,那这个数就有很多位置可以放,相反,如果在所有比他小的数的外面,那就只能放在一个位置。

我们设正在考虑的数为 kkxxmin[pos0posk]\min{[\text{pos}_0 \ldots \text{pos}_k]}yymax[pos0posk]\max{[\text{pos}_0 \ldots \text{pos}_k]},如果 kk[x,y][x, y] 这个区间外面,那么 kk 就只能放在 posk\text{pos}_k 上,否则,可以选择 [x,y][x, y] 中任意一个没被占用的地方放置。

我们设每个数能选的位置的数量为 did_i,那么最终的答案就是所有的 dd 乘起来,也就是 i=0n1\prod_{i = 0}^{n - 1}

代码

在具体实现的时候,可以从 00 开始一个一个的考虑,这样可以很方便的确定前面提到的 xxyy,以及 [x,y][x,y] 区间内,被占用的位置的数量。

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// keywords:
const int MOD = 1e9 + 7;
int main() {
int t;
cin >> t;

while (t--) {
int n;
cin >> n;
int a[n + 1];
int pos[n + 1];
for (int i = 0; i < n; i++) {
cin >> a[i];
pos[a[i]] = i;
}
ll l = pos[0], r = pos[0];
ll ans = 1;
for (int i = 1; i < n; i++) {
// l 和 r 就是之前讲的 x, y
if (pos[i] < l)
l = pos[i];
else if (pos[i] > r)
r = pos[i];
//如果在 x, y 的外面
else
ans = ans * (r - l + 1 - i) % MOD;
}
cout << ans << endl;
}
}

最后,希望这篇题解对你有帮助,如果有问题可以通过评论区或者私信联系我。