题解：CF 1909F1 - 小排列问题（简单版本）

问题重述

给定长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，其中 $0 \le a_i \le n$。
求满足下列条件的 $1 \sim n$ 的排列 $p_1, p_2, \dots, p_n$ 的数量：

对于每个 $i$，前缀 $[p_1, p_2, \dots, p_i]$ 中值不超过 $i$ 的元素个数恰好等于 $a_i$。

答案对 $998244353$ 取模。

关键观察

1. 必要条件

   • 整个排列中所有 $n$ 个数都不超过 $n$，因此 $a_n$ 必须等于 $n$。
   • $a_i$ 必须是非递减的，并且 $0 \le a_i \le i$。
   • 相邻差值 $d_i = a_i - a_{i-1}$（规定 $a_0 = 0$）只能为 $0, 1$ 或 $2$。
     理由：考虑从 $i-1$ 到 $i$，新加入的区域是第 $i$ 行和第 $i$ 列（交点为 $(i,i)$）。该区域最多能容纳 $2$ 个新点（因为每行每列只能有一个点）。

2. 网格模型
   将排列 $p$ 视为 $n \times n$ 网格上的 $n$ 个点，坐标为 $(i, p_i)$。
   那么条件“前缀 $[p_1,\dots,p_i]$ 中值 $\le i$ 的个数为 $a_i$”等价于：

   在左上角 $i \times i$ 的子网格中，恰好有 $a_i$ 个点。

   设 $cur = a_{i-1}$，我们已经在前 $(i-1)\times(i-1)$ 的区域内放置了 $cur$ 个点。
   由于排列的性质，这 $cur$ 个点占据了 $cur$ 行和 $cur$ 列。我们可以将这些行/列重新编号为 $1..cur$，即认为它们已经占据了左上角 $cur \times cur$ 的方块（不影响计数）。

3. 空闲行列数
   在 $i-1$ 步后，已经占用了 $cur$ 行和 $cur$ 列，所以剩下的空闲行和空闲列各有：

这些空闲行/列分别对应编号 $\text{cur}+1$ 到 $i-1$。

第 $i$ 步的转移

第 $i$ 步新增的可放置区域由三部分组成：

• 第 $i$ 行前 $i-1$ 列：其中只有 $\text{free}$ 列是空闲的（因为被占用的列不能放新点）。
• 第 $i$ 列前 $i-1$ 行：其中只有 $\text{free}$ 行是空闲的。
• 格子 $(i,i)$：总是空闲的。

令 $d = a_i - a_{i-1}$。根据 $d$ 的值，我们有三种情况：

• $d = 0$：不添加任何点，方案数乘 $1$。
• $d = 1$：恰好添加一个点。有三种选择：
  • 放在 $(i,i)$：$1$ 种。
  • 放在第 $i$ 行的某个空闲列：$\text{free}$ 种。
  • 放在第 $i$ 列的某个空闲行：$\text{free}$ 种。
    总方案数为 $1 + 2\cdot\text{free}$。
• $d = 2$：必须添加两个点，一个在第 $i$ 行（非交点），一个在第 $i$ 列（非交点）。
  设第 $i$ 行的点在第 $c$ 列，第 $i$ 列的点在第 $r$ 行，其中 $r$ 和 $c$ 必须从 $\text{free}$ 个空闲行/列中选择。
  任意有序对 $(r, c)$ 都合法（允许 $r=c$），故方案数为 $\text{free}^2$。

合法性检查

• 若 $a_n \ne n$，直接输出 $0$。
• 遍历 $i=1..n$ 时，若出现 $d < 0$ 或 $d > 2$ 或 $\text{free} < 0$，则无解。

算法步骤

1. 读入 $t$。
2. 对每个测试用例：
   • 读入 $n$ 和数组 $a[1..n]$。
   • 若 $a[n] \neq n$，输出 $0$ 并继续。
   • 初始化 $ans = 1$，$cur = 0$（表示 $a_{i-1}$）。
   • 对于 $i = 1$ 到 $n$：
     • 计算 $d = a[i] - cur$，若 $d \notin \{0,1,2\}$，标记非法。
     • 计算 $\text{free} = i-1 - cur$，若 $\text{free} < 0$，标记非法。
     • 根据 $d$ 更新 $ans$：
       • $d=0$：不变
       • $d=1$：$ans = ans \times (1 + 2\cdot\text{free}) \bmod MOD$
       • $d=2$：$ans = ans \times (\text{free}^2) \bmod MOD$
     • 更新 $cur = a[i]$。
   • 若未出现非法，输出 $ans$，否则输出 $0$。

复杂度

每个测试用例 $O(n)$，所有测试用例的 $n$ 之和不超过 $2\times 10^5$，因此总复杂度 $O(\sum n)$，非常高效。

代码实现（C++）

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

const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];

        if (a[n] != n) {
            cout << "0\n";
            continue;
        }

        long long ans = 1;
        int cur = 0; // a[i-1]
        bool ok = true;

        for (int i = 1; i <= n; ++i) {
            int d = a[i] - cur;
            if (d < 0 || d > 2) {
                ok = false;
                break;
            }
            int free = i - 1 - cur;
            if (free < 0) {
                ok = false;
                break;
            }
            if (d == 1) {
                ans = ans * (1 + 2LL * free) % MOD;
            } else if (d == 2) {
                ans = ans * (1LL * free * free % MOD) % MOD;
            }
            cur = a[i];
        }

        cout << (ok ? ans : 0) << '\n';
    }
    return 0;
}

验证样例

输入：

5
5
1 2 3 4 5
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15

输出：

1
4
0
0
532305727

与题目示例完全一致。