U558844 小苯的排列计数

题目信息

• 题目：U558844 小苯的排列计数
• 来源：洛谷
• 链接：U558844 小苯的排列计数
• 标签：数学、计数、前缀最小值
• 模数：$998244353$

---

题意简述

给定一个长度为 $n$ 的数组 $\mathrm{prefix}$。

其中：

$${\mathrm{prefix}}_i=\min \{p_1,p_2,\dots ,p_i\}$$

也就是说，${\mathrm{prefix}}_i$ 表示排列 $p$ 的前 $i$ 个元素中的最小值。

现在需要统计有多少个 $1\sim n$ 的排列 $p$，能够生成给定的前缀最小值数组。

如果不存在符合条件的排列，输出 $0$。

---

样例理解

以样例：

4
2 2 1 1

为例。

前缀最小值为：

$$\begin{array}{rl}{\mathrm{prefix}}_1& =2\\ {\mathrm{prefix}}_2& =2\\ {\mathrm{prefix}}_3& =1\\ {\mathrm{prefix}}_4& =1\end{array}$$

第一位的前缀最小值是 $2$，说明：

$$p_1=2$$

第三位时，前缀最小值从 $2$ 下降到 $1$，说明：

$$p_3=1$$

剩下的位置不能改变当前前缀最小值，因此只能填入比当前最小值更大的数字。

符合条件的排列有：

2 4 1 3
2 3 1 4

所以答案为 $2$。

---

核心思路

这题的关键是理解：

前缀最小值下降的位置是固定位置；前缀最小值不变的位置是自由位置。

---

规律一：最后一个前缀最小值必须是 1

因为 $p$ 是一个 $1\sim n$ 的排列，所以整个排列的最小值一定是 $1$。

因此：

$${\mathrm{prefix}}_n=1$$

如果：

$${\mathrm{prefix}}_n\ne 1$$

那么一定不存在合法排列，答案为 $0$。

例如：

2 2

长度为 $2$ 的排列一定包含数字 $1$，最终前缀最小值不可能还是 $2$，所以无解。

---

规律二：前缀最小值数组必须单调不增

随着位置向后移动，前缀范围只会变大，最小值不可能变大。

因此必须满足：

$$\forall i\ge 2,{\mathrm{prefix}}_i\le {\mathrm{prefix}}_{i-1}$$

如果出现：

$${\mathrm{prefix}}_i>{\mathrm{prefix}}_{i-1}$$

则说明前缀最小值变大了，这是不可能的，答案为 $0$。

---

规律三：下降位置的数字是固定的

如果：

$${\mathrm{prefix}}_i<{\mathrm{prefix}}_{i-1}$$

说明第 $i$ 个位置产生了新的前缀最小值。

那么当前位置只能填：

$$p_i={\mathrm{prefix}}_i$$

例如：

6 2 2 1 1 1 1

其中：

$${\mathrm{prefix}}_1=6$$

所以：

$$p_1=6$$

然后：

$${\mathrm{prefix}}_2=2<6$$

所以：

$$p_2=2$$

再然后：

$${\mathrm{prefix}}_4=1<2$$

所以：

$$p_4=1$$

这些位置都已经被固定。

---

规律四：不下降的位置只能填更大的未使用数字

如果：

$${\mathrm{prefix}}_i={\mathrm{prefix}}_{i-1}$$

说明当前位置没有产生新的最小值。

设当前前缀最小值为 $x$，那么当前位置填入的数字必须满足：

$$p_i>x$$

否则如果填入：

$$p_i<x$$

前缀最小值就会下降，与给定的 $\mathrm{prefix}$ 不符。

同时，$p_i$ 还必须是没有使用过的数字。

---

计数方式

我们先找出所有出现在 $\mathrm{prefix}$ 中的数字。

这些数字中，第一次出现的位置都是固定位置，不能当作自由数字使用。

剩下没有出现在 $\mathrm{prefix}$ 中的数字，才可以填入那些前缀最小值不变的位置。

设：

$$freeGreater[x]$$

表示：

大于 $x$，并且没有出现在 $\mathrm{prefix}$ 中的数字数量。

即：

$$freeGreater[x]=\#\{v\mid v>x,v\notin \mathrm{prefix}\}$$

当扫描到一个重复位置：

$${\mathrm{prefix}}_i={\mathrm{prefix}}_{i-1}$$

设：

$$x={\mathrm{prefix}}_i$$

那么当前位置可以选择的数字数量为：

$$freeGreater[x]-usedFree$$

其中：

$$usedFree$$

表示前面已经用掉的自由数字数量。

每处理一个重复位置，就将答案乘上当前可选数量。

---

算法步骤

1. 读入 $\mathrm{prefix}$ 数组；
2. 记录哪些数字出现在了 $\mathrm{prefix}$ 中；
3. 判断 $\mathrm{prefix}$ 是否单调不增；
4. 判断 ${\mathrm{prefix}}_n$ 是否等于 $1$；
5. 预处理 $freeGreater[x]$；
6. 从左到右扫描 $\mathrm{prefix}$；
7. 遇到相等位置时计算可选数字数量；
8. 累乘答案并取模。

---

复杂度分析

设当前测试点的长度为 $n$。

预处理 $freeGreater$ 需要 $O(n)$。

扫描 $\mathrm{prefix}$ 也需要 $O(n)$。

因此总时间复杂度为：

$$O(n)$$

空间复杂度为：

$$O(n)$$

由于题目保证所有测试数据的 $n$ 之和不超过 $3\times 10^5$，该复杂度可以通过。

---

参考代码

/**
 * Problem: U558844 小苯的排列计数
 * URL: https://www.luogu.com.cn/problem/U558844
 * Memory Limit: 512 MB
 * Time Limit: 1000 ms
 */
 
#if defined(__APPLE__) && defined(__MACH__)
#include <iostream>
#include <vector>
#include <algorithm>
#else
#include <bits/stdc++.h>
#endif
 
using namespace std;
 
using LL = long long;
 
const LL MOD = 998244353;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T;
    cin >> T;
 
    while (T--) {
        int n;
        cin >> n;
 
        vector<int> prefix(n + 1);
        vector<bool> appeared(n + 1, false);
 
        // 读取 prefix，并记录哪些数字在 prefix 中出现过
        for (int i = 1; i <= n; i++) {
            cin >> prefix[i];
            appeared[prefix[i]] = true;
        }
 
        bool ok = true;
 
        // prefix 必须单调不增
        for (int i = 2; i <= n; i++) {
            if (prefix[i] > prefix[i - 1]) {
                ok = false;
            }
        }
 
        // 整个排列的最小值一定是 1
        if (prefix[n] != 1) {
            ok = false;
        }
 
        /**
         * freeGreater[x] 表示：
         * 大于 x，且没有出现在 prefix 中的数字数量。
         *
         * 这些数字可以被用在 prefix 不下降的位置。
         */
        vector<int> freeGreater(n + 2, 0);
 
        for (int x = n - 1; x >= 1; x--) {
            freeGreater[x] = freeGreater[x + 1];
 
            int v = x + 1;
 
            if (!appeared[v]) {
                freeGreater[x]++;
            }
        }
 
        LL ans = 1;
 
        // 已经使用过的自由数字数量
        LL usedFree = 0;
 
        for (int i = 2; i <= n; i++) {
            // prefix 不变，说明当前位置需要填入一个大于当前最小值的自由数字
            if (prefix[i] == prefix[i - 1]) {
                int x = prefix[i];
 
                LL choices = freeGreater[x] - usedFree;
 
                if (choices <= 0) {
                    ok = false;
                    break;
                }
 
                ans = ans * choices % MOD;
                usedFree++;
            }
        }
 
        cout << (ok ? ans : 0) << '\n';
    }
 
    return 0;
}

---

易错点

1. 最后一个值必须是 1

排列一定包含数字 $1$，所以最终前缀最小值一定是 $1$。

如果没有判断：

$${\mathrm{prefix}}_n=1$$

就会把一些不合法情况算进去。

---

2. 前缀最小值只能不增

前缀范围扩大后，最小值不可能变大。

所以必须判断：

$${\mathrm{prefix}}_i\le {\mathrm{prefix}}_{i-1}$$

---

3. 数组要开到 n + 1

因为数字范围是：

$$1\sim n$$

所以像 appeared、freeGreater 这类数组都应该至少开到 n + 1。

不要写成：

vector<bool> appeared(n, false);

否则访问 appeared[n] 时会越界。

---

4. 不要用双重循环暴力统计可选数字

如果每次遇到重复位置，都重新扫描一遍 $1\sim n$，最坏复杂度会退化成：

$$O(n^2)$$

数据范围最大时会超时。

应该预处理：

$$freeGreater[x]$$

让每次查询变成 $O(1)$。

---

复盘

这题表面上是在还原排列，实际上是一个计数问题。

关键不是枚举排列，而是区分两类位置：

1. 前缀最小值下降的位置：数字已经固定；
2. 前缀最小值不变的位置：需要从可用自由数字中选择。

只要能正确统计每个自由位置的可选数字数量，就可以直接累乘得到答案。

核心公式是：

$$choices=freeGreater[x]-usedFree$$

其中 $x$ 是当前前缀最小值，usedFree 是前面已经用掉的自由数字数量。