「GFOI Round 2」Aob & Blice

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

题意

定义一个排列

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

CPP

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

「GFOI Round 2」Aob & Blice

文章操作

题意

题解

Code

相关推荐

评论

「GFOI Round 2」Aob & Blice