正经题解｜相似排列

提示1

设 $p[x]$ 是 $x$ 在排列 $a$ 中的位置（下标）。

由于 $MEX([a_{p[0]}])=1$，所以 $0$ 在排列 $b$ 中的位置只能是 $p[0]$。

提示2

$1$ 可以放在排列 $b$ 中的什么位置？

提示3

假设 $p[0] < p[1]$；
如果 $p[2] < p[0]$，$2$ 可以放在排列 $b$ 中的哪些位置？
如果 $p[2] > p[1]$，$2$ 可以放在排列 $b$ 中的哪些位置？
如果 $p[0] < p[2] < p[1]$，$2$ 可以放在排列 $b$ 中的哪些位置？

题目解析

令 $p[x]$ 为 $x$ 在排列 $a$ 中的位置（下标）。

由于 $MEX([a_{p[0]}])=1$，所以 $0$ 在排列 $b$ 中的位置只能是 $p[0]$。

接下来讨论 $1$ 可以放在排列 $b$ 中的位置。

假设 $p[0] < p[1]$，那么
对于所有区间 $[l, r](l \le p[0] < p[1] \le r)$，有 $MEX([b_l, \ldots, b_r]) > 1$;
对于其他区间 $[l, r](p[0] \le l \le r \le p[1])$，有 $MEX([b_l, \ldots, b_r]) \le 1$ 。

所以，$1$ 必然只能放在 $p[1]$ 这个位置。

我们以一个更具体的例子来说明：

假设 $p[0] < p[1]$，不难发现以下性质:
A. 对于区间 $[p[0], p[1]]$, 有 $MEX([b_{p[0]}, \ldots, b_{p[1]}]) > 1$；
B. 对于区间 $[p[0], x](p[0] < x < p[1])$，有 $MEX([b_{p[0]}, \ldots, b_{x}]) = 1$。
若 $b_{p[1]} \neq 1$，令 $x$ 为 $1$ 在 $b$ 中的位置，考虑以下两种情况：
1. $x < p[0]$ 或 $p[1] < x$:
此时 $x$ 在区间 $[p[0], p[1]]$ 外，此时 $MEX([b_{p[0]}, \ldots, b_{p[1]}]) = 1$ 与 $A$ 矛盾。
2. $p[0] < x < p[1]$:
此时 $x$ 在区间 $[p[0], p[1]]$ 内，此时 $MEX(b_{p[0]}, \ldots, b_{x}) > 1$ 与 $B$ 矛盾。

将区间 $[p[0], p[1]]$ 作为当前区间 $[l, r]$ 并继续考虑 $2$ 可以放在排列 $b$ 中的位置。

若 $p[2] \in [l, r]$，那么
对于所有区间 $[x, y](x \le l < r \le y)$，有 $MEX([b_x, \ldots, b_y]) > 2$；
对于其他区间 $[x, y](l < x \le y < r )$，有 $MEX([b_x, \ldots, b_y]) \le 2$。

只要 $2$ 在区间 $[l, r]$ 内就能够满足以上两个条件，所以 $2$ 可以放在区间 $[l, r]$ 内的任何一个位置（除了已经被占用的位置），所以当 $p[2] \in [l, r]$ 时，$2$ 可以放置的位置数量为 $(r - l + 1) - 2$。

否则，$2$ 只能放在排列 $b$ 中的 $p[2]$ 这个位置上。并且当前区间被扩展至包含 $p[2]$，变为 $[p[2], r]$ 或 $[l, p[2]]$。

容易看出后续的数字 $3, 4, \ldots, n - 1$ 都可以这样处理。

令 $k$ 为当前处理的数字，若 $k \in [l, r]$，说明 $k$ 可以放置的位置数量为 $(r - l + 1) - k$。否则将当前区间扩展至包含 $p[k]$。

最终问题的答案就是每个元素可以放置位置数量的乘积。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> a(n), b(n);
        for (auto &x : a) cin >> x;
        for (int i = 0; i < n; ++i)
            b[a[i]] = i;
        int l = b[0], r = b[0], res = 1;
        for (int i = 1; i < n; ++i) {
            if (b[i] < l)
                l = b[i];
            else if (b[i] > r)
                r = b[i];
            else
                res = res * (r - l + 1LL - i) % MOD;
        }
        cout << res << '\n';
    }
    return 0;
}

复杂度分析

对于数字 $0$ 可以放在排列 $b$ 中的位置唯一，并可以将当前区间 $[l, r]$ 初始化为 $[p[0], p[0]]$，之后按照顺序处理剩余的 $n-1$ 个数字即可，时间复杂度为 $O(n)$。