CF 1699C The Third Problem

标签: cf

有一个 的排列 。求有多少个排列 st 每一个 ,有

表示 在排列 中的位置。考虑枚举 的值。如果 一定包含了 的所有值,因此这个 应当满足 。同时,为了保证 相同,对于值 ,如果 ,则在 中, 可以放在 的任意一个位置,否则必须放在与 相同的位置。

void solve()
{
    int n;
    scanf("%d", &n);
    std::vector<int> a(n);
    for (auto &i : a) scanf("%d", &i);
    std::vector<int> pos(n);
    for (int i = 0; i < n; i++)
        pos[a[i]] = i;
    int l = pos[0], r = pos[0];
    long long ans = 1;
    for (int i = 1; i < n; i++)
    {
        if (l <= pos[i] && pos[i] <= r) ans = ans * (r - l + 1 - i) % MODN; // 注意减去已经安排好位置的 i 个元素.
        l = std::min(l, pos[i]);
        r = std::max(r, pos[i]);
    }
    printf("%lld\n", ans);
}