题解：P11281 「GFOI Round 2」Aob & Blice
FlyPancake
·
·
题解
P11281 「GFOI Round 2」Aob & Blice 题解
本题解对于结论有较为理性的证明。
题目太长太抽象自己看。
因为会随机抽且经过无限轮，所以对某一排列 p 有对于任意的 1 \le x < y \le n 且 p_x > p_y，均会产生二元组 (x, y) 和 (p_x, p_y)。
考虑何时才能使 $p$ 满足条件：
- 对于 A 何时能产生二元组 $(y, x)$，因为 $x < y$，所以只能由满足 $p_m=x, p_t=y$ 且 $t<m$ 的情况产生。
- 对于 A 何时能产生二元组 $(p_y, p_x)$，因为 $p_x > p_y$，所以只能由满足 $p_{p_x} < p_{p_y}$ 的情况产生。
对于条件一，此时也满足 $p_{p_t} < p_{p_m}$，于是题意转化成为：
对于一个 $1 \sim n$ 的排列 $p$，$p$ 满足平局条件当且仅当对于任意 $1 \le i < j \le n$ 且 $p_i > p_j$，需满足 $p_{p_i} < p_{p_j}$。
（此处证明放最后）
所以 $p$ 满足平局条件，当且仅当 $p_{p_i} = i$。
接下来考虑如何求出方案数：
若不满足平局条件，则输出 $0$。
已知的数满足平局条件之后，记此时仍可以为 $0$ 的数的个数为 $cnt$。对于 $1 \le i \le cnt$，记 $dp_i$ 为前 $i$ 个数的总方案数。
- 假设 $p_i = i$，则 $dp_i = dp_{i-1}$。
- 假设 $p_i \neq i$，则需从 $1 \sim i-1$ 中选一个数与 $i$ 互相匹配，有 $i-1$ 种可能，剩下的之前确定的方案数为 $dp_{i-2}$，所以 $dp_i = dp_{i-2} \times (i-1)$。
综上，转移方程为 $dp_i = dp_{i-1}+dp_{i-2}\times (i-1)$。显然有 $dp_0 = dp_1 = 1$。
答案即为 $dp_{cnt}$。
---
参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N = 1e6+5, mod = 998244353;
int n, p[N];
int dp[N], cnt;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++)
cin>>p[i];
for(int i=1; i<=n; i++){
if(p[i]){
if(!p[p[i]]) p[p[i]] = i;
else if(p[p[i]] != i){
cout<<0;
return 0;
}
}
}
for(int i=1; i<=n; i++)
if(!p[i]) cnt++;
dp[0] = 1; dp[1] = 1;
for(int i=2; i<=cnt; i++)
dp[i] = (dp[i-1]+(ll)dp[i-2]*(i-1)%mod)%mod;
cout<<dp[cnt];
return 0;
}
```
---
关于上文中的证明：
已知有 $1 \sim n$ 的排列 $p$，对于任意 $1 \le i < j \le n$ 且 $p_i > p_j$，均有 $p_{p_i}<p_{p_j}$，才能使 $p$ 符合平局条件。
记 $P_i(x)$ 表示 $i$ 经过 $x$ 次取 $p$ 中的值后得到的值。例如 $P_i(1)=p_i, P_i(2)=p_{p_i}$。
因为 $P_i(1) > P_j(1)$ 且 $P_i(2) < P_j(2)$，所以 $P_i(3) > P_j(3)$。
因为 $P_i(2) < P_j(2)$ 且 $P_i(3) > P_j(3)$，所以 $P_i(4) < P_j(4)$。
以此类推。
将 $P_i(2)=i$ 看作二元环，下面证明对于任意三元环不存在 $p$ 符合条件：
若 $1 \le i < j \le n$ 且 $P_i(1) > P_j(1)$，则 $P_i(4) < P_j(4)$。而根据三元环的性质 $P_i(1) = P_i(4)$，与满足条件矛盾，故不成立。
对于任意奇数环同理可证。
下面证明对于任意四元环不存在 $p$ 符合条件：
若 $1 \le i < j \le n$ 且 $P_i(1) > P_j(1)$，一定存在 $P_i(2)=j, P_j(2)=i$，因为对于任意一个数均有一个位置与之对应而且必定有 $i<j$ 的情况，此时需满足 $P_i(2)<P_j(2)$，即 $j<i$，与已知矛盾。
对于任意偶数环同理可证。