我十分支持出题人改人名的行为（因为省选真的很难

Solution

入手之后看题，不难发现这个随机是没有用的，在无限轮的加持下，Aob 会选完所有可能的逆序对或逆序对下标，即 (p_x,p_y) 或 (x,y)，同样 Blice 会跟随 Aob 选完所有的 (y,x) 或 (p_y,p_x)。这里的能选就选很容易说明，Blice 不选完会导致 |S_B| < |S_A|，所以 Blice 也是能选就选。

这样我们稍微知道了我们需要求的是什么，但进入计算还是很遥远不好想，我们从样例入手：

3
0 2 0

它的答案是 2。

7
0 3 2 0 5 7 0

它的答案是 2，而且满足的情况必有 p_7=6。

同时，我们自己构造一个数据

3
2 1 3

他的答案是 0。

然后观察三组数据（也可以结合 n=4 的情况进一步探讨），我们发现：有这样的序列必然有：

对于位置 x，要么有 x=p_x，要么有 p_{p_x}=x

这就是我们所发现的性质，即两两必然配对（相等的情况算广义）。然后我们从 n=3 的所有不成立情况结合数学归纳法，稍微理解一下就能证明一般的 n 同样有这样的性质。这里笔者只是简单的推了一下，因为笔者的数学功底很差并没有极度严格的证明，有兴趣的话可以尝试自己证一下。

有了这个性质，我们的前路豁然开朗。剩下的工作便只有判无解和推出有 k 个不确定排列元素（要求两两配对）的总方案数了。判无解很简单，寻找是否有 x=p_x 或 p_{p_x} = x 即可，当 p_{p_x} = 0 时令 p_{p_x} \gets x 即可，否则直接输出 0。

剩下就是考虑推出有解的答案。令 dp_k 为有 k 个不确定元素时的方案数。打表一下发现有 dp_0=1,dp_1=1,dp_2=2,dp_3=3 似乎像是可以递推的样子，那么就直接上动态规划。

考虑 DP，尝试写出转移方程，我们要由 dp_1 \sim dp_{n-1} 推出 dp_n，分情况讨论：

1. n=p_n$ 这时候跟前面无影响，方案数为 $dp_{n-1}

转移方程即为：

dp_n=dp_{n-1}+(n-1)\times dp_{n-2}

这道题到这里就做完了，时间复杂度 O(n)。

code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1e6 + 514;
constexpr ll mod = 998244353;

namespace Otakus
{
    int n, a[N], A[N], cnt = 0;
    ll dp[N];

    void init()
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];

        for (int i = 1; i <= n; i++)
        {
            if (i != a[i] && a[i] != 0)
            {
                if (!a[a[i]])
                    a[a[i]] = i;
                else if (a[a[i]] != i)
                {
                    cout << 0;
                    return;
                }
            }
        }

        for (int i = 1; i <= n; i++)
            if (!a[i])
                cnt++;

        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= cnt; i++)
            dp[i] = (dp[i - 1] + (i - 1) * dp[i - 2]) % mod;

        cout << dp[cnt];
    }
} // namespace Otakus

int main()
{

    Otakus::init();
    return 0;
}