题解：P11281 「GFOI Round 2」Aob & Blice

引流。

本人数学不好，语言可能不严谨，望大佬指出 QwQ

这道题看起来很复杂，但其实是诈骗题。

首先不难发现 p_x,p_y 是一个逆序对。接着，为了确保无论 Aob 怎么选，Blice 都可以使最终自己选的数集与 Aob 完全一致，我们发现：对于所有逆序对 p_x,p_y(x<y)，都有：p_x=y,p_y=x。这样，无论 Aob 选了 (x,y) 还是 (p_x,p_y)，Blice 都可以做到与 Aob 选的一致。

为什么呢？我们不妨用反证法进行证明：

如果一个逆序对 p_x,p_y(x<y) 其中 p_x=a,p_y=b 满足 a \neq y 或 b \neq x，那么只要 Aob 一直选择这一对中的 (a,b)，Blice 就肯定无法做到与 Aob 完全一致。

根据题目中“无限轮”后平局的定义，当逆序对数为 x、轮数为 n 时，易构造出 \varepsilon=(2x)^{-n}，根据上述不平局的策略，我们发现不平局的出现概率至少为 (2x)^{-n}（即 Aob 每次都选择 (a,b)），与题目中对“无限轮”后平局的定义矛盾。

所以能够使 Aob 和 Blice “无限轮”后平局，p_i 必须满足：

知道这个后，我们就可以开始考虑代码实现了。

首先显然可以记录下每个数 x 在 p 中出现的位置 r_x，如果出现 r_x \neq p_x，说明不可能平局，输出 0 即可。否则我们可以统计剩下有多少个数能填，对这些数我们求出满足上述两条规则的数列个数即可。

统计剩下有多少个数能填时要注意分类和细节：

1. 若 p_x=x，则能填的数少一。

2. 若 p_x=0 但 r_x \neq 0，说明 p_{r_x}=x 那么此时 p_x 只能填 r_x，那么 p_x 不能填，能填的数少一。

3. 若 p_x \neq 0，由于已经判断过无解，那么 p_x 不能填，能填的数少一。

接下来看如何计算答案。假设还能填的数有 cnt 个，考虑递推求出答案。设 f_x 表示前 x 个数有多少种合法的填法，易发现：对于第 x+1 个数，如果它满足条件一（p_x=x），则有 f_x 中可行的填法；如果它满足条件二（p_x=y,p_y=x），那么它必须从前 x 个数中再选一个，再填剩下的数，即有 x \cdot f_{x-1} 种。有次我们你可以得出：

判断无解是 \mathcal{O}(n) 的，计算 cnt 是 \mathcal{O}(n) 的，递推求 f_{cnt} 也是 \mathcal{O}(n) 的，总时间复杂度 \mathcal{O}(n)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e6+5;
const ll mod=998244353;
const ll inv=499122177;
int n,a[N],r[N];
ll f[N];

int main() {
    scanf("%d",&n);
    int cnt=n;
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        if(!a[i]) continue ;
        r[a[i]]=i;
    }
    for(int i=1;i<=n;i++) {
        if(r[i]&&(r[i]!=a[i]&&a[i])) return printf("0\n"),0;
        else if(r[i]) cnt--;
        else if(r[a[i]]) cnt--;
    }
    f[0]=f[1]=1LL;
    for(int i=2;i<=cnt;i++) {
        ll x=i;
        f[i]=(f[i-1]+f[i-2]*(x-1LL)%mod)%mod;
    }
    printf("%lld\n",f[cnt]);
    return 0;
}