Solution Of P11281「GFOI Round 2」Aob & Blice

Dr1fty · 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;
}