题解：AT_arc219_b [ARC219B] Reverse Permutation

DrDuck · 2026-05-13 20:46:03 · 题解

可以发现，想让 Q 反转后的排列 P 字典序最小，肯定是找到第一个 Q_i \ne i 的 i，然后找到位置 j 使得 Q_j = i，然后把区间 [i,j] 翻转，这样数 i 就到了前面。

因此，我们可以枚举 i 满足 \forall j \in [1,i],a_j=j，即比 i 小的数都已经不能再优化字典序，然后我们假设 Q 不是从 1 到 n 的排列，这样的话 i 不能满足 Q_i = i，不然的话肯定去后面翻转一个比 i 大的数去优化字典序了，这样在 Q 中 i 就可能出现在 [i+1,n] 的位置，有 n - i 种方案数。如果 Q 可以是从 1 到 n 的排列有点特殊，这需要满足 P 也是从 1 到 n 的排列，这个特判掉。

:::success[CODE]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e+5 + 5, mod = 998244353;
int T, n;
int a[maxn];
void GOGOGO() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) {
        cout << 1 << '\n';
        return;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == i) {
            ans = (ans + n - i) % mod;
            if (i == n) ans = (ans + 1) % mod;
        }
        else break;
    }
    cout << ans << '\n';
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--) GOGOGO();
    return 0;
}

:::