专栏文章

Solution Of P11281「GFOI Round 2」Aob & Blice

DDr1fty
P11281题解参与者 69已保存评论 90

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
90 条
当前快照
1 份
快照标识符
@mir4nj5a
此快照首次捕获于
2025/12/04 15:41
3 个月前
此快照最后确认于
2025/12/04 15:41
3 个月前
查看原文

Preface

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

Solution

我们直接考虑在游戏轮数趋于无穷时的情况。
此时，我们注意到所有的 (x,y)(x,y) 和 (px,py)(p_x, p_y) 都会被 Aob 加入 SAS_{A}，那么为了让 SA=SBS_{A}=S_{B}，因此所有的 (x,y)(x,y) 和 (px,py)(p_x, p_y) 都必须能够通过 Blice 的两种选择产生。
我们看一下 Blice 基于 Aob 能产生的三种数对，分别是 (y,x),(py,px),(ppy,ppx)(y,x),(p_y,p_x),(p_{p_y},p_{p_x})，那么形式化的，我们就可以把在游戏轮数趋于无穷时的的 SAS_{A}，SBS_{B} 写出来。
SA={(x,y),(px,py)∣1≤x<y≤n,px>py}S_A =\left \{(x,y),(p_x,p_y)\mid 1\le x < y\le n,p_x > p_y \right \} SB={(y,x),(py,px),(ppy,ppx)∣1≤x<y≤n,px>py}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 \}
然后我们会注意到，SA=SBS_A=S_B 的充分必要条件†^†是 ∀1≤i≤n\forall 1\le i\le n 都有 ppi=ip_{p_i} = i。这样也就解决掉了性质 A，即利用结论判定一下 pp 是否满足所述条件即可。
接下来我们考虑如何统计方案。
首先为了满足条件，有一些 00 上必须填上固定的数。对于满足 ppi=0p_{p_i} = 0 的 ii，为了满足条件 ppip_{p_i} 必须填上 ii。那么在这样填完之后，我们还会剩下若干个 00，那么我们可以把这些 00 单独拿出来求方案数，设剩下 kk 个 00，那么方案数显然等价于对于所有的 1∼k1\sim k 的排列 qq 中，满足 ∀1≤i≤n\forall 1\le i\le n 都有 ppi=ip_{p_i} = i 的 qq 的个数。
然后我们考虑递推求解，设方案数为 fkf_k，则不难发现 f1=1,f2=2f_1 = 1, f_2 = 2。对于当前的 qkq_k，若 qk=kq_k=k，这种情况下方案数由 fk−1f_{k-1} 直接转移而来，否则必定要选出一个 1≤j<k1\le j<k，使得 qqk=jq_{q_k} = j 然后共有 n−1n-1 种选法，且选出的 k,jk,j 是独立于其他数的，那么对于每一种选法都有 fk−2f_{k-2} 的方案，此时总数为 (k−1)fk−2(k-1)f_{k-2}。两种情况合并，就得出了递推式 fi=fi−1+(i−1)fi−2f_i=f_{i-1}+(i-1)f_{i-2}，其中 i>2i>2。答案就是 fkf_k。
下面给出对于 †† 的证明：
我们发现命题实际上等价于建立一个有向图 G⟨V,E⟩G\left \langle V,E\right \rangle，其中：
V=x∣1≤x≤n,x∈ZV={x\mid 1\le x\le n,x\in \Z}
E=(i,pi)∣1≤i≤n,i∈ZE={(i,p_i)\mid 1\le i\le n, i\in \Z}
那么 SA=SBS_A=S_B 当且仅当 GG 中不存在长度超过 22 的环。
  • 先证必要性：
    你会发现对于所有 1≤x<y≤n,px>py1\le x < y\le n,p_x > p_y，有 (x,y)=(py,px),(px,py)=(y,x),(ppy,ppx)=(y,x)(x,y) = (p_y, p_x),(p_x, p_y) = (y,x),(p_{p_y}, p_{p_x}) = (y, x)，证好了。
  • 再证充分性：
    考虑反证，若不满足条件，此时图中必定存在节点数大于三的一个环，不妨设这个环的节点编号集为 M={u1,u2,…,uk}M=\{u_1, u_2,\dots,u_k\}，我们记 MM 所能产生在 SAS_A 的 {(x,y),(px,py)}=TA\{(x,y),(p_x,p_y)\} = T_A，能在 SBS_B 中产生的 {(y,x),(py,px),(ppy,ppx)}=TB\{(y,x),(p_y,p_x),(p_{p_y}, p_{p_x})\} = T_B，那么我们由定义显然有 x∈M,y∈M,px∈M,py∈Mx\in M, y\in M,p_x\in M, p_y\in M，因此 TAT_A 和 TBT_B 是封闭的。所以若 SA=SBS_A=S_B 那么 TA=TBT_A = T_B。
    我们不妨设 u1<u2<⋯<uku_1<u_2<\dots<u_k，因此 (uk−1,uk)∈TA(u_{k-1},u_{k})\in T_A，但是由穷举可得，(uk−1,uk)(u_{k-1},u_{k}) 一定不属于 TBT_B（由于 pui=ui+1(1≤i<k),puk=u1p_{u_i} = u_{i + 1}(1\le i < k),p_{u_k} = u_1 因此你只要穷举 (uk−2,uk−1),(uk,uk−1),(uk,u1)(u_{k-2},u_{k-1}),(u_{k}, u_{k-1}),(u_{k}, u_1) 对 TBT_B 能贡献的数对，这显然是极其有限的，因此可以直接穷举），于是矛盾，证毕。

Code

CPP
#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;
}

评论

共 90 条评论，欢迎与作者交流。

正在加载评论...