Small Permutation Problem (Easy Version)

Yorg / 2024-10-12 / 原文

算法

考虑转化
每个点 $p_i$ 在一个平面直角坐标系中表示为点 $(i, p_i)$

于是转化为一个棋盘问题, 即每一个点不能在同一行 / 同一列
$a$ 数组的限制相当于在左下角为 $(0, 0)$, 右上角为$(i, i)$ 中的正方形中, 有 $a_i$ 个棋子

于是在每一次加入的时候, 都只能在一个 L 型区域的符合要求的地方加入

例如此时就只能在红色区域加入

于是可以分类讨论(此处 $a_i$ 均为差分数组)

当 $a_i = 0$, 则代表没有增加任何点对, 答案不变
当 $a_i = 1$, 则代表增加了一个点对, 有 $2 \times i - 1 - 2 \times a_{i - 1}$ 种可能的选择, 将其乘入答案
当 $a_i = 2$，则代表增加了两个点对, 每个点有 $i - 1 - a_{i - 1}$ 种可能的选择, 将其的平方乘入答案

代码

#include <bits/stdc++.h>
#define int long long
const int MAXN = 2e5 + 20;
const int MOD = 998244353;

int T;
int n;
int a[MAXN];
int d[MAXN];

int Ans = 1;

void solve()
{
    Ans = 1;
    for (int i = 1; i <= n; i++)
    {
        if(d[i] == 0)
        {
            continue;
        }else if(d[i] == 1)
        {
            Ans = ((Ans % MOD) * ((2 * i - 1 - 2 * a[i - 1]) % MOD)) % MOD;
        }else if(d[i] == 2)
        {
            Ans = (Ans % MOD) * ((i - 1 - a[i - 1]) % MOD) * ((i - 1 - a[i - 1]) % MOD) % MOD;
        }
    }
}

signed main()
{

    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
            d[i] = a[i] - a[i - 1];
        }

        solve();
        printf("%lld\n", Ans);
    }

    return 0;
}