题解 CF2207E2 【N-MEX (Counting Version)】

Leasier · 2026-03-09 18:49:51 · 题解

• 请先查看同场 E1 的题解。

下面对每个 i 分类讨论：

• (a) a_i = a_{i - 1}：要选一个 < a_i、与后面的 a_j 皆不同、且与后面 a_j = a_{j - 1} 对应的 b_j 皆不同的项，方案数为 a_i - (n - i)。
• (b) a_i < a_{i - 1}：要选一个 \geq a_{i - 1} 或被用过的数。
• _注：前一篇题解已经证明：讨论 a_i 时，取出 \{0, \cdots, n\} \backslash a 中没有被用过的最大数，其一定 < a_i。_
• 故而，待选集合恰由前面的 a_j 和与前面 a_j = a_{j - 1} 对应的 b_j 组成，方案数为 i。

综上，将每一步的方案数相乘即可。时间复杂度为 O(\sum n)。

代码：

#include <stdio.h>

const int mod = 1e9 + 7;
int a[200001];

void solve(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++){
        int need = (a[i] + 1) - (n - i + 1);
        if (need < 0 || need > i){
            printf("0\n");
            return;
        }
    }
    a[0] = n;
    for (int i = 1; i <= n; i++){
        if (a[i] > a[i - 1]){
            printf("0\n");
            return;
        }
    }
    int ans = 1;
    for (int i = 1; i <= n; i++){
        if (a[i] == a[i - 1]){
            ans = 1ll * ans * (a[i] - (n - i)) % mod;
        } else {
            ans = 1ll * ans * i % mod;
        }
    }
    printf("%d\n", ans);
}

int main(){
    int t;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; cas++){
        solve();
    }
    return 0;
}