题目看起来很吓人，似乎无从下手。可以看成一个优先队列，每次加入一个数，弹出最小值。
注意到 \(K\) 范围为 \(10^9\)，尝试从化简 \(K\) 范围入手。
发现当 \(K > N - M + 1\) 时，数字 \(N - M + 2 \dots N\) 始终处于优先队列中，并在最后有序排成一段。
当操作完 \(N - M + 1\) 次后，接下来 \(K - (N - M + 1)\) 次操作中，每次相当于从后面取一个数放到这 \(M - 1\) 个数的前面。
所以，对于 \(K > N - M + 1\) 的情况，我们可以转化为 \(K = N - M + 1\) 的情况。这样化简还有一个好处，就是可以断环为链。
这样，问题的模型就很简洁了，去掉了许多繁琐的条件。
对于第 \(i\) 次操作，发现 \(b_i\) 取值为 \(\min(a_{1\dots i + K - 2} \text{ 中的第 } i \text{ 小值 }, a_i)\)。
这样，当 \(b_i\) 为前缀最大值，有 \(K\) 个空位供选择，否则只能是 \(a_i\)。
最后再乘上 \(N - M + 2 \dots N\) 这些数的排列方案数 \((M - 1) !\)，时间复杂度 \(O(N)\)。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb push_back
using namespace std;
const ll maxn = 3e5 + 10, mod = 998244353;
ll n, m, k, a[maxn], b[maxn], ans = 1;
int main() {
scanf("%lld%lld%lld", &n, &m, &k);
for(ll i = 0; i < n; i++) scanf("%lld", a + i);
if(k > n - m + 1) {
ll t = k - (n - m + 1); memcpy(b, a, sizeof a);
for(ll i = 1; i < m; i++)
a[i + n - m] = b[(i + t + n - m) % n];
for(ll i = 0; i <= n - m; i++)
a[i] = b[(i + (t + n - m - i)
/ (n - m + 1) * (n - m + 1)) % n];
k = n - m + 1;
}
for(ll i = n; i; i--) a[i] = a[i - 1];
ll ok = 1;
for(ll i = 1; i < m; i++)
ok &= (a[k + i] > a[k + i - 1]);
for(ll i = 1; i <= k; i++)
ok &= (a[i] < a[k + 1]);
if(!ok) { puts("0"); return 0; }
for(ll i = 1, mx = 0; i <= k; i++)
if(a[i] > mx) ans = ans * m %mod, mx = a[i];
for(ll i = 1; i < m; i++) ans = ans * i %mod;
printf("%lld", ans);
return 0;
}