题解：AT_arc219_b [ARC219B] Reverse Permutation

xiaozhengguoaaa · 2026-05-14 06:33:01 · 题解

第二题受了影响不敢做了。

结果切了。

思路及推导

思路

线性扫描。

合法排列 Q 满足对其进行一次区间反转后得到的字典序最小排列为 P。

首先判定如果 P_1 \neq 1 则答案为 0。

随后找到最大的 k 使得 \forall 1 \le i \le k,P_i=i。

然后下面的 ans 会在下面推导一遍。

那答案就是为 ans = k \cdot n - \dfrac{k(k+1)}{2}，当 k=n 时答案自增 1，最终结果对 998244353 取模。

推导

若 k = n，答案额外加 1，就是 ans = k \cdot n - \frac{k(k+1)}{2} + [k=n]。

:::info[AC code]

#include <bits/stdc++.h>
#define int long long
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 4e6 + 7;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
// const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
// const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int dx[] = {-1 , 1 , 0 , 0} ;
const int dy[] = {0 , 0 , -1 , 1} ;

inline int read ()
{
    int s = 0 , w = 1 ;
    char ch = getchar () ;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar () ;
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0' ;
        ch = getchar ();
    }
    return s * w ;
}
inline void write (int x)
{
    if (x < 0) putchar ('-') , x = -x ;
    if (x > 9) write (x / 10) ;
    putchar (x % 10 + '0') ;
    return ;
}

signed main()
{
    fst ;
    int t ;
    cin >> t ;
    while (t --)
    {
        int n ;
        cin >> n ;
        vector<int > p(n) ;
        for (int i = 0 ; i < n ; i ++)
        {
            cin >> p[i] ;
        }
        if (p[0] != 1)
        {
            cout << 0 ;
            cout << endl ;
            continue ;
        }
        int k = 1 ;
        while (k < n && p[k] == k + 1)
        {
            k ++ ;
        }
        int ans = 1LL * k * n - 1LL * k * (k + 1) / 2 ;
        if (k == n)
        {
            ans ++ ;
        }
        ans %= MOD ;
        cout << ans << endl ;
    }
    return 0;
}

:::