P11281 题解

发表于 阅读次数：

本人数学不好，语言可能不严谨，望大佬指出 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$ 必须满足：

  1. $p_i=i$。

  2. $p_i=j$ 同时 $p_j=i$（$i \neq j$）

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

首先显然可以记录下每个数 $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}$ 种。有次我们你可以得出：

$f_{x+1}=f_x+x \cdot f_{x-1}$

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}