自动搬运

查看原文

来自洛谷，原作者为

	Drifty zzzzzzᙆᙆᙆᙆᙆᙆ

搬运于2025-08-24 23:06:03，当前版本为作者最后更新于2024-11-16 18:55:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Preface

神秘的好题。

虽然棕名但求过，之前公开赛大小号交同一份代码棕了。本人并不存在抄袭。

Solution

我们直接考虑在游戏轮数趋于无穷时的情况。

此时，我们注意到所有的 $(x,y)$ 和 $(p_x, p_y)$ 都会被 Aob 加入 $S_{A}$，那么为了让 $S_{A}=S_{B}$，因此所有的 $(x,y)$ 和 $(p_x, p_y)$ 都必须能够通过 Blice 的两种选择产生。

我们看一下 Blice 基于 Aob 能产生的三种数对，分别是 $(y,x),(p_y,p_x),(p_{p_y},p_{p_x})$，那么形式化的，我们就可以把在游戏轮数趋于无穷时的的 $S_{A}$，$S_{B}$ 写出来。

$$S_A =\left \{(x,y),(p_x,p_y)\mid 1\le x < y\le n,p_x > p_y \right \} $$$$S_B =\left \{(y,x),(p_y,p_x),(p_{p_y},p_{p_x})\mid 1\le x < y\le n,p_x > p_y \right \} $$

然后我们会注意到，$S_A=S_B$ 的充分必要条件$^†$是 $\forall 1\le i\le n$ 都有 $p_{p_i} = i$。这样也就解决掉了性质 A，即利用结论判定一下 $p$ 是否满足所述条件即可。

接下来我们考虑如何统计方案。

首先为了满足条件，有一些 $0$ 上必须填上固定的数。对于满足 $p_{p_i} = 0$ 的 $i$，为了满足条件 $p_{p_i}$ 必须填上 $i$。那么在这样填完之后，我们还会剩下若干个 $0$，那么我们可以把这些 $0$ 单独拿出来求方案数，设剩下 $k$ 个 $0$，那么方案数显然等价于对于所有的 $1\sim k$ 的排列 $q$ 中，满足 $\forall 1\le i\le n$ 都有 $p_{p_i} = i$ 的 $q$ 的个数。

然后我们考虑递推求解，设方案数为 $f_k$，则不难发现 $f_1 = 1, f_2 = 2$。对于当前的 $q_k$，若 $q_k=k$，这种情况下方案数由 $f_{k-1}$ 直接转移而来，否则必定要选出一个 $1\le j<k$，使得 $q_{q_k} = j$ 然后共有 $n-1$ 种选法，且选出的 $k,j$ 是独立于其他数的，那么对于每一种选法都有 $f_{k-2}$ 的方案，此时总数为 $(k-1)f_{k-2}$。两种情况合并，就得出了递推式 $f_i=f_{i-1}+(i-1)f_{i-2}$，其中 $i>2$。答案就是 $f_k$。

下面给出对于 $†$ 的证明：

我们发现命题实际上等价于建立一个有向图 $G\left \langle V,E\right \rangle$，其中：

$$V={x\mid 1\le x\le n,x\in \Z}$$ $$E={(i,p_i)\mid 1\le i\le n, i\in \Z}$$

那么 $S_A=S_B$ 当且仅当 $G$ 中不存在长度超过 $2$ 的环。

• 先证必要性：

  你会发现对于所有 $1\le x < y\le n,p_x > p_y$，有 $(x,y) = (p_y, p_x),(p_x, p_y) = (y,x),(p_{p_y}, p_{p_x}) = (y, x)$，证好了。

• 再证充分性：

  考虑反证，若不满足条件，此时图中必定存在节点数大于三的一个环，不妨设这个环的节点编号集为 $M=\{u_1, u_2,\dots,u_k\}$，我们记 $M$ 所能产生在 $S_A$ 的 $\{(x,y),(p_x,p_y)\} = T_A$，能在 $S_B$ 中产生的 $\{(y,x),(p_y,p_x),(p_{p_y}, p_{p_x})\} = T_B$，那么我们由定义显然有 $x\in M, y\in M,p_x\in M, p_y\in M$，因此 $T_A$ 和 $T_B$ 是封闭的。所以若 $S_A=S_B$ 那么 $T_A = T_B$。

  我们不妨设 $u_1<u_2<\dots<u_k$，因此 $(u_{k-1},u_{k})\in T_A$，但是由穷举可得，$(u_{k-1},u_{k})$ 一定不属于 $T_B$（由于 $p_{u_i} = u_{i + 1}(1\le i < k),p_{u_k} = u_1$ 因此你只要穷举 $(u_{k-2},u_{k-1}),(u_{k}, u_{k-1}),(u_{k}, u_1)$ 对 $T_B$ 能贡献的数对，这显然是极其有限的，因此可以直接穷举），于是矛盾，证毕。

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int P = 998244353, N = 1e6 + 3;
int n, p[N], x = 1;
i64 res[N] = {0, 1, 2}, ans;
int main() {
    cin.tie(nullptr), cout.tie(nullptr) 
    -> sync_with_stdio(false); cin >> n;
    for (int i = 1; i <= n; i ++) cin >> p[i];
    for (int i = 1; i <= n; i ++) if (p[p[i]] != i) x = 0;
    if (x) return cout << 1, 0;
    for (int i = 1; i <= n; i ++) if (p[i]) {
        if (p[p[i]] == 0) p[p[i]] = i;
        else if (p[p[i]] != i) return cout << 0, 0;
    }
    for (int i = 1; i <= n; i ++) if (!p[i]) ans ++;
    for (int i = 3; i <= n; i ++)
        res[i] = (res[i - 1] + res[i - 2] * (i - 1) % P) % P;
    return cout << res[ans], 0;
}