题解：AT_arc219_b [ARC219B] Reverse Permutation
C202301
·
·
题解
前言
这不比 A 简单？
做法
观察一下，一次操作等价于说遍历 i \in [1,n]，找到最小的 i 满足 a_i \not = i，然后把 i 旋转上去。
然后再考虑 P。从 1 到 n 遍历，由于原排列假设 [1,j] 都满足 a_j =j，那么初始排列最长就是 [1,j-1] 都是满足 a_i=i 的。而发现如何旋转分类都本质不同，也就是假设第一个不等于的是 i，则有 n-i 种方案。不过要特判满足 i \in [1,n], a_i=i 的情况。
如果还没有理解，比如说样例 a=[1,2,6,4,5,3]，则假设初始 a_1 \not = 1，则可能方案为：
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 998244353, N = 5e5;
ll n, a[N + 5], t;
void solve() {
scanf("%lld", &n);
for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
ll ans = 0;
for(ll i = 1; i <= n; ++i) {
if(i != a[i]) break;
if(i == n) {
(ans += 1) %= mod;
} else {
(ans += n - i) %= mod;
}
}
printf("%lld\n", ans);
}
int main() {
cin >> t;
while(t--) {
solve();
}
return 0;
}
```