cf：C. The Third Problem【关于排列这件事】

分析

这是一道排列的题
看起来花里胡哨的
说到排列，我们就要找到这个排列0到n对应的下标位置
我们这里的MET定义是除字串外最小的数，所有的字串都要满足这个最小的数相同
于是，我们遵循“最小”，从最小的0开始一个个找对应的索引
首先0的位置肯定变不了，其次1也变不了（否则总能找到一个区间使得MET不等）
然后看2后面的数，用lr维护当前索引区间的左右，然后如果2在lr中的话，它就有r - l + 1 - 2种选择
如果它在索引区间lr外，那么必定有一种区间的选择使得MET不等，为了更形象，举个例子：
+++2+++1+++0+（1）
++2++++1+++0+（2）
----+++++++++++
如果我们选上一行+的区间，那显然MET（1） > 2而 MET（2） = 2
因此当我们选第k个数的时候，上一个lr索引区间长度是r - l + 1
我们只有当id[i]在索引区间内才可以相似，这时候它能选的位置个数共有r - l + 1 - i
用ans 连乘就可以了

ac code

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    id = [0] * n
    for i, v in enumerate(a):
        id[v] = i
    # we judge from v = 0,1,...
    ans = 1
    l = r = id[0]
    for i in range(1, n):
        # if id[i] outside [l, r], no other choice
        # cause there must be a choice MET not equal
        if id[i] < l or id[i] > r:
            l, r = min(id[i], l), max(id[i], r)
        else:
            ans = ans * (r - l + 1 - i) % MOD
    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

排列 + 排序 + 区间内外模拟
通过排除一些情况从而猜测合理的情况