自动搬运

查看原文

来自洛谷，原作者为

	CarroT1212 chrono::system_clock::now().time_since_epoch().count()

搬运于2025-08-24 23:08:27，当前版本为作者最后更新于2025-01-11 23:17:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我擦，企鹅罐！生存战略！

挺好的性质题。写详细亿点。

排列可以看成有向环集合来计数。设在 $p$ 上对于每个 $i$，在图上连接 $i\leftrightarrow p_i$ 得到的无向图为 $G_1$，在 $a$ 上对于每个 $i$ 连接 $i\to a_i$ 得到的有向图为 $G_2$。那么 $a$ 合法仅当 $G_1$ 的每条边的其中一个方向都在 $G_2$ 中出现。$G_1$ 已知了，我们需要知道合法的 $G_2$ 数，考虑刻画。

首先由于 $a$ 是排列，$G_2$ 只包含有向环，那么 $G_1$ 出现一个度数 $\ge 3$ 的点就包没合法 $G_2$ 的。考虑到 $G_1$ 出来会是个基环森林，都不能有森林了，看起来 $G_1$ 也必须是一堆环构成的啊？

（观察样例）发现有个奇怪情况：$G_1$ 里有二元环。你会发现这里我们应该要将这个二元环当作一条无向边来看待，因为 $G_2$ 只需要有一条有向边就可以同时消灭二元环里的两条边。

于是把二元环换成无向边后 $G_1$ 里出现了链！现在看看怎么个事。

• $G_1$ 中有点度数 $\ge 3$，无解。
• 对于 $G_1$ 中的自环，不用管它，它在 $G_2$ 里还是自环。
• $G_1$ 中点数 $\ge 3$ 的环，在 $G_2$ 中这些边都需要出现，每个环都有两种定向方法，统计环数 $k$ 最后乘上 $2^k$。
• $G_1$ 中的链，我们在 $G_2$ 中需要给每条链定向，然后用若干条有向边把它们的两端连接起来，变成若干有向环集合。设链数为 $x$，要是把定向完的链看成一个大点，那这个连接过程其实就是根据一个长度为 $x$ 的排列建 $G_2$ 的过程，连接方案数为 $x!$（每条链定向完后只有一个点能接受入边，一个点输出出边，而外部新连的边的方向已经根据连接情况确定）。而每条链内部有两种定向方式，再乘上 $2^x$……

别急，还有高手！如果 $G_2$ 里又连出了二元环，这时这个环的两种定向方式在 $G_2$ 里看起来是一样的！算重到起飞！

这种情况要求 $G_1$ 里存在一个孤单的二元环被变成了一条无向边，然后我们在后期连接的时候直接将它的两端连了起来。设 $G_1$ 中这样单独的一条无向边作一条链的条数为 $y$。

没事还可以容斥，我们钦定其中 $i$ 条边在 $G_2$ 里被当成二元环的另一个方向算重的方案数为 $f_i$。有 $f_i=\binom{y}{i}2^{x-i}(x-i)!$。最后 $ans=2^k\sum\limits_{i=0}^y(-1)^if_i$。

实现就是看看 $G_1$ 里上面几种东西都有几种，算就完了。小心漏了什么阴间情况。

const ll J=1e18,N=1e6+7,P=998244353;
ll qp(ll x,ll y=P-2) { return y?(y&1?x:1)*qp(x*x%P,y>>1)%P:1; }
ll fac[N],fnv[N];
struct init { init() {
	fac[0]=1; for (ll i=1;i<N;i++) fac[i]=fac[i-1]*i%P;
	fnv[N-1]=qp(fac[N-1]); for (ll i=N-1;i;i--) fnv[i-1]=fnv[i]*i%P;
} } A;
ll C(ll x,ll y) { return x<0||y<0||x<y?0:fac[x]*fnv[y]%P*fnv[x-y]%P; }
ll n,a[N],ans,vis[N];
ll c3,c21,c22;
vector<ll> e[N];
void no() { cout<<"0",exit(0); }
void get(ll p) {
	if (e[p].size()>1) no();
	vis[p]=1;
	if (e[p].size()==1&&!vis[e[p][0]]) get(e[p][0]);
}
void mian() {
	scanf("%lld",&n);
	for (ll i=1;i<=n;i++) scanf("%lld",&a[i]),e[a[i]].pb(i);
	for (ll i=1;i<=n;i++) if (!vis[i]) {
		if (a[i]==i) {
			if (e[i].size()>1) no();
			vis[i]=1;
		}
		else if (a[a[i]]==i) {
			ll x=i,y=a[i],flg=0;
			vis[x]=vis[y]=1;
			if (e[x].size()>2||e[y].size()>2) no();
			if (e[x].size()==2) flg=1,get(e[x][0]^e[x][1]^y);
			if (e[y].size()==2) flg=1,get(e[y][0]^e[y][1]^x);
			flg?c22++:c21++;
		}
	}
	for (ll i=1;i<=n;i++) if (!vis[i]) {
		if (!e[i].size()) no();
		c3++,get(i);
	}
	ll ans=0;
	for (ll i=0;i<=c21;i++) (ans+=(i&1?P-1:1)*C(c21,i)%P*qp(2,c21+c22-i)%P*fac[c21+c22-i])%=P;
	cout<<ans*qp(2,c3)%P;
}