「GFOI Round 2」Aob & Blice

羊羊君的幻想 · 2024-11-17 18:30:06 · 题解

题目 Link

幽默绿题卡了我一个半小时，写篇题解鞭尸一下自己。

题意

定义一个排列 p 的逆序对集合 \begin{aligned}S=\left\{ (i,j),(p_i,p_j) | i<j,p_i>p_j \right\}\end{aligned}。

定义 \begin{aligned}S'=\left\{ (j,i),(p_j,p_i) | i<j,p_i>p_j \right\}\end{aligned}；

求有多少种排列 p，使得 S\subseteq S'。

翻译过来就是求有多少个排列 p 满足：对于所有逆序对 (i,j),(p_i,p_j) 中的这两组有序数对全部放入一个集合里，且对于所有 (j,i) 和 (p_j,p_i) 都能在这个集合中找到。

题解

此题的后效性显然，故不去考虑 DP，考虑使用排列组合解决问题。

先说结论：对于一个满足题目要求的排列 p，当且仅当对于任意的正整数 i，满足 p_{p_i}=i。

翻译过来就是，对于一个位置 i ，上面的数字为 p_i，位置为 p_i 上的数字为 i。

下面给出证明。

初始状态定义为 \forall i,p_i=i，即排列为单调递增的 1,2,...,n。此时排列 p 一定合法，因为没有逆序对， S=\varnothing；
考虑将排列中的两个数 x 和 y 交换位置，此时，p_x =y 且 p_y =x，不妨设 x<y；
容易发现，这产生了一些逆序对（下面的叙述建立在交换后的状态）： x < (x+1 \sim y),y> (x\sim y-1) 和 (x+1 \sim y-1) < y,(x+1,y-1)>x；
容易发现 S' 恰好等于 S；
此时接着分讨，在除了 x 和 y 的所有数中进行交换，共三种情况，很复杂，但是讨论之后容易发现，这三种交换情况最后都是符合条件的；
但是如果把 x 和 y 中的任意一个和别的数交换了，很容易发现该排列不再满足题目条件。

综上，我们得出结论：所有的合法状态都来自于初始状态的交换。

下面结合图片更好理解。

回到题目，我们需要先判断是否有解再去计算方案数。

判断有解就是判断对于 i，如果数字 p_i 在位置 i 上，则万事大吉，反之：

如果数字 i 在位置 p_i 上，也无妨，合法；
如果数字 i 没有出现过，那么把它填在位置 p_i 上。
如果数字 i 出现过还没有填在位置 p_i 上，则必定无解，答案为 0。

剩下的，就是计算将没填的数拎出来填上，具体方法如下：

首先显而易见，设当前没填的数字为 i，则位置 i 一定是空缺的。然后把所有的数字 i 全部填到对应的位置 i 上。
对于刚才填进去的数字，我们可以挑出一部分两两匹配，剩下的留在原位置。
直接暴力计数即可。

所以，我们可以线性枚举有多少个数字留在原位置，剩下的数字两两交换，\mathcal{O}(1) 计算方案。

设共 m 个数两两匹配的方案数为 p_m，则 p_2=1，显然 m 只能为偶数，不然必定会有一个数留在原位置。

考虑由 m 递推到 m+2，发现可以先把第一个数和剩下 m+1 个数中随便找一个匹配，剩下的 m 个数自由匹配，得到递推式 p_{m+2}=p_{m}*(m-1)。

由于我们枚举有多少个数留在原位置，这个数的奇偶性是确定的。

设最终我们要把 k 个数填进去，设 i 为留在原位置的数的个数，则答案为：

\sum_{i=1}^{k} C_k^{i}*p_{k-i}

且要求 i 的奇偶性与 k 相同。

时间复杂度 \mathcal{O}(n)。

具体结合代码理解。

Code

#include<bits/stdc++.h>
#define int long long
#define pb push_back
namespace IO{
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
        return x*f;
    }
}
using namespace IO;
using namespace std;
const int N=1e6+10;
const int mod=998244353;
int a[N],pos[N];
int n;
bool vis[N];
int f[N];
int df[N];
int ksm(int x,int p){
    int ret=1;
    while(p){
        if(p&1) ret=1LL*ret*x%mod;
        x=1LL*x*x%mod;
        p>>=1;
    }   
    return ret;
}
int C(int x,int y){
    if(y==0) return 1;
    return f[x]*df[y]%mod*df[x-y]%mod;
}
int p[N];
signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]!=0) pos[a[i]]=i;
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            if(pos[i]&&!pos[pos[i]]){
                a[i]=pos[i];pos[pos[i]]=i;
            }else if(pos[i]&&pos[pos[i]]){
                puts("0");return 0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(i!=a[i]){
            if(pos[i]!=a[i]){
                puts("0");return 0;
            }
        }
        if(!a[i]) ++cnt;
    }
    f[0]=1;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1]*i%mod;
    }
    df[n]=ksm(f[n],mod-2);
    for(int i=n-1;i>=0;i--){
        df[i]=df[i+1]*(i+1)%mod;
    }
    int ans=0;
    p[0]=1;
    for(int i=2;i<=n;i+=2){
        p[i]=(i-1)*p[i-2]%mod;
    }
    if(cnt&1){
        for(int i=1;i<=cnt;i+=2){
            ans=(ans+C(cnt,i)*p[cnt-i]%mod)%mod;
        }
    }else{
        for(int i=0;i<=cnt;i+=2){
            ans=(ans+C(cnt,i)*p[cnt-i]%mod)%mod;
        }
    }

    cout<<ans;
return 0;
}