CF1677D Tutorial

Aleph_Drawer · 2024-06-06 10:28:21 · 题解

我是 *2500 都不会的傻子。这题还是挺套路的题。

首先很容易注意到一个 v 能够唯一确定一个 a。具体证明可以考虑从后往前一位一位的确定。接下来就和 a 没有任何关系了。

首先注意到必须满足 v_i < i。否则 v 不合法。

考虑题目描述的流程在做什么事情。本质上就是一次“冒泡”的过程。简单观察一下，考虑一个数 a_i，每次一定会有一个比 a_i 大的数越过这个位置，并挪到后面的位置。这个表现在 v 上就是，v_i 往左边挪了一个位置，值变成了 v_i - 1。第 n 个位置空了出来，显然是相对的最值，应当补一个 0。

有了这个就相当好做了。首先检查 v 的合法性。注意到除了要满足 v_i < i 之外，还要满足后 k 个位置必须是 0。如果这两个条件有一个不满足答案就是 0。

我们已经知道一次“冒泡”操作是 v'_i \leftarrow \max(v_{i + 1} - 1, 0)。现在我们想还原回去。

首先我们要整体右移，然后在第一个位置补上一个 -1。对于原先已经有的 -1 我们不管它；对于 v_i > 0 的，显然在移动之后的 v' 之中只有一个确定值 v_i + 1；对于 v_i = 0 的情况则略微复杂。考虑移动 k 次之后的情况，此时 v_i = 0 的位置的取值可能为 [0, k] 之间的任意一个。

事实上，我们只需要计数，那么我们并不需要模拟上述过程。

我们只需要考虑 1 \sim n - k 位，对于 v_i = -1 的位置，在最初的 v 中可能的取值范围是 [0, i + k - 1]；对于 v_i = 0，在最初的 v 中可能的取值范围是 [0, k]；对于 v_i > 0，在最初的 v 中的取值只有一种 v_i + k。我们只需要做一做简单的乘法即可。最后别忘了给答案乘上 k!，因为最开始前面有 k 个 -1。

哎呀，语言表述真是稀碎。看代码得了。

// Author : Aleph_Drawer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6 + 105;
const ll MOD = 998244353;

int t;
int n, k;
int v[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> t;
    for(; t; --t) {
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
            cin >> v[i];
        ll ans = 1;
        for(int i = 1; i <= n; i++) {
            if(v[i] >= i) ans = 0;
        }
        for(int i = n; i >= n - k + 1; i--)
            if(v[i] != 0 && v[i] != -1) ans = 0;
        if(ans == 0) {
            cout << "0\n"; continue;
        }
        for(int i = 1; i <= k; i++)
            ans *= i, ans %= MOD;
        for(int i = 1; i <= n - k; i++) {
            if(v[i] == -1) ans *= (i + k), ans %= MOD;
            if(v[i] == 0) ans *= (k + 1), ans %= MOD;
        }
        cout << ans << '\n';
    }
    return 0;
}