AT_arc149_e 题解

· · 题解

AT_arc149_e

思路

好题，在和 @Bellala 老师的讨论下懂了。

首先看题目，考虑对于一个初始序列 A 是怎么进行操作的。

观察到，在第 n-m+1 轮操作以后，所有点都被考虑过了，此时整个序列最后 m-1 个数一定是最大的 m-1 个数，此后每次操作相当于将除去最大的几个数的数循环位移一格。此时如果我们把最大的 m-1 个数组成的集合拎出来，后续操作就是把剩下的数排成序列，并进行循环位移。

如果操作数不足 n-m+1 个，则剩下的没有进行操作的数是没有办法改变的，因此我们将前面的数离散化后又可以变成 K=n-m+1 的情况了。

现在只需要考虑 K=n-m+1 的情况。

这时候在第 i 轮操作时，我们相当于是携带了 A_0 \sim A_{m-1+i} 的最大的 m-1 个数的集合，然后把 A_{m+i} 加入集合，把集合里的最小元素填进 B_{i}。考虑和第一种情况相同的建模方法，我们同样将操作集合拎出来得到一个新序列，那么现在的操作就是把序列的第一个数加进操作集合，然后把操作集合的最小数放在序列末尾。

考虑转换成计数。

首先考虑无解的情况，因为你能够得知操作集合的位置了，而操作集合在原最终序列中的体现一定是升序的。所以只要不是，就无解。

然后，考虑新最终序列上的每一个数 B_i。如果这个数前面存在一个 B_j \gt B_i ，那么因为一个更大的数都被弹掉了，所以操作集合中在加入这个数前不存在比 B_j 小的数，因此一定是加入后立刻弹出，所以新初始序列 A_{i+m}=B_i。否则，那么说明他可以填在任意一个还未被确定的位置上（有 m 个），所以对答案的贡献是 m。

最后在乘上一个最大 m-1 个值的随机排列数即可。

总结

可以固定一个动的位置来观测过程。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 10;
const ll P = 998244353;
int n, m, K, b[N];
int tmp[N];
int main() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 0; i < n; i++) scanf("%d", b + i);
    if (K < n - m + 1) {
        n = n - (n - m + 1 - K);
        for (int i = 0; i < n; i++) tmp[i] = b[i];
        sort(tmp, tmp + n);
        int cnt = unique(tmp, tmp + n) - tmp;
        for (int i = 0; i < n; i++) b[i] = lower_bound(tmp, tmp + cnt, b[i]) - tmp + 1;
    }//离散化
    int st = K % n, rev = K % (n - m + 1);
    rotate(b, b + st, b + n);
    //还原最后多余的操作
    rotate(b + m - 1, b + n - rev, b + n);
    //构建模型，其中前 m-1 个是操作集合，后面是新序列
    ll ans = 1;
    for (int i = 0; i < m - 1; i++) {
        if (b[i] != n - m + i + 2) {
            printf("0\n");
            return 0;
        }//无解
        ans = ans * (i + 1) % P;
    }
    int mx = 0;
    for (int i = m - 1; i < n; i++) {
        if (b[i] > mx) {
            mx = b[i];
            ans = ans * m % P;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
// AT_arc149_e