题解：CF1909F1 Small Permutation Problem (Easy Version)

又是一个水蓝题 好像不难 为什么我不会

首先要注意到$a$想要有答案必须满足这样的条件：

$$0 \leq a_{i + 1} - a_i \leq 2$$

$0 \leq a_{i + 1} - a_i$ 是因为每一个小于等于 $i$ 的数肯定小于等于 $i + 1$ 。

$a_{i + 1} - a_i \leq 2$ 是因为在 $1$ 到 $i$ 中大于 $i$ 且小于等于 $i + 1$ 的数只可能有一个（也就是 $i + 1$ ）然后你再把一个小于 $i + 1$ 的数放在 $i + 1$ 这个位置，差值就达到了最大的 $2$ 。

那对于从 $1$ 到 $n - 1$ 的每个$i$我们来分别讨论三种情况：

• $a_{i + 1} - a_i = 0$ ：在$i + 1$这个位置放入了一个比$i + 1$大的数，答案不变。

• $a_{i + 1} - a_i = 1$ ：$i + 1$ 放入 $\left [1, i \right ]$ 或者一个小于 $i + 1$ 的数放入 $i + 1$ 这个位置，对答案的贡献分别是 $\left (i - a_i \right )$ 和 $\left (i + 1 - a_i \right )$ 。

• $a_{i + 1} - a_i = 2$ : $i + 1$被放入$\left [ 1, i \right ]$ 且一个小于 $i + 1$ 的数放入 $i + 1$ 这个位置，对答案的贡献分别是 $\left (i - a_i \right )$ 和 $\left (i + 1 - a_i - 1 \right )$。

然后从前往后乘一下做完了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (a[1] > 1) {
        cout << 0 << '\n';
        return;
    }
    int ans = 1;
    for (int i = 1; i < n; i++) {
        if (a[i + 1] - a[i] < 0 || a[i + 1] - a[i] > 2) {
            ans = 0;
            break;
        }
        if (a[i + 1] - a[i] == 1) {
            ans = (ans * ((i - a[i]) + (i + 1 - a[i]))) % mod;
        } else if (a[i + 1] - a[i] == 2) {
            ans = ((ans * (i - a[i])) % mod * (i + 1 - a[i] - 1)) % mod;
        }
    }
    cout << (a[n] == n ? ans : 0) << '\n';
    return;
}
signed main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}