[ARC149E] Sliding Window Sort

考虑到 \(k \le 10^9\) 太大了，我们先模拟一下看看能不能化成 \(k\) 比较小的情况。注意到，我们每次只会在 \(i\) 留下一个数，相当于我们手上一定有前缀前 \(m - 1\) 大的数。这样当我们操作完 \([n - m, n - 1]\) 时，手上就会有 \([n - m + 1, n]\)，然后后面的操作就确定为了每次把 \(a_{k + m - 1}\) 移到 \(k\) 的位置上。这样我们可以先判掉不合法情况，然后把 \([n - m + 1, n]\) 这些数排除掉，求出最终整个序列发生了怎样的变化，这样就转化为了 \(k = n - m + 1\) 的情形。

然后发现若 \(k < n - m + 1\)，那么后缀就是确定的，对答案无影响，直接令 \(n = k + m - 1\) 即可。现在就固定有 \(k = n - m + 1\) 了。

现在只用考虑一个序列上的问题，考虑 \(b_i\) 合法的充要条件，相当于 \(a_{1,2,3\cdots i + m - 1}\) 中排除掉 \(b_{1,2,3\cdots i-1}\) 后剩下的数中有一个 \(b_i\) 并且全部 \(\ge b_i\)。自然想到若 \(b_{i - 1} > b_i\) 则 \(b_i\) 只能填在 \(a_{i + m - 1}\) 这个位置上，因为前面的位置都 \(\ge b_{i - 1} > b_i\)。进一步当且仅当 \(b_i\) 为前缀 \(\max\) 时有 \(m\) 种方案，其余情况都只能填在 \(a_{i + m - 1}\) 上，这个可以利用上面的性质按照距离前一个前缀 \(\max\)归纳证明。

最后 \([n - m + 1, n]\) 这些数还有 \((m - 1)!\) 种方案。复杂度 \(O(n)\)。

const int N = 3e5 + 10;
const int P = 998244353;
int n, m, k;
int b[N];

int main() {
  read(n, m, k);
  for(int i = 0; i < n; ++i)
    read(b[i]);
  if(n > m + k - 1) n = m + k - 1;
  vector<int> tmp(b, b + n);
  sort(tmp.begin(), tmp.end());
  for(int i = 0; i < n; ++i)
    b[i] = lower_bound(tmp.begin(), tmp.end(), b[i]) - tmp.begin() + 1;
  int ans = m;
  for(int i = 1, j = (m + k - 2) % n; i < m; ++i, j = (j - 1 + n) % n)
    if(b[j] != n - i + 1) ans = 0;
  k -= n - m + 1;
  int pos = (n - 1ll * (k + n - m) / (n - m + 1) * (m - 1) % n) % n;
  int mx = b[pos];
  for(int i = 1, j = pos; i <= n - (m - 1); ++i, j = (j + 1) % n) {
    while(b[j] > n - m + 1) j = (j + 1) % n;
    if(b[j] > mx) mx = b[j], ans = 1ll * ans * m % P;
  }
  for(int i = 1; i < m; ++i) ans = 1ll * ans * i % P;
  printf("%d\n",ans);
}