雅虎曰：原题传送门

题意不需要翻译吧。

分析

我们考虑给对应数字所在的卡片建边。

那么我们会发现，生成的图肯定是若干个连通块，每个连通块都恰好是一个环（或者单独一个点）。而每一条边的两边都至少要取一个点。

所以我们只需要考虑，每一个环有多少种方案，最后根据乘法原理把它们相乘就可以了。

不难发现，环的贡献只与环的大小有关。我们设 $f[i]$ 表示总共有 $i$ 个点的环的方案数。

这个东西看着就像一个 DP 的样子······所以我们尝试一下：经过列举以后发现：$f[1] = 1, f[2] = 3, f[3] = 4, f[4] = 7, f[5] = 11$，不难猜出一个结论：

$$f[i] = f[i - 1] + f[i - 2]$$

这个结论的证明，我是参考了 lfyszy 大佬的方法的：

假设环上总共有 $n$ 个点，其中有三个点：$A$ 点，它两边的 $B$ 点和 $C$ 点，环上剩余的部分用 $O$ 表示。

那么，我们考虑是否选 $A$ 点。

• 选 $A$ 点

那么 $B$ 点和 $C$ 点就可以任取了，所以这个环就变成了一个 $B + O + C$ 的链，这个链不好计算，我们不妨作一条辅助线——连接 $BC$。作完辅助线以后，这个图的答案就是 $f[n - 1]$，但是我们还漏算了一种情况，就是 $B,C$ 两个点都不取的情况。我们把这两个点压成一个点 $P$。我们设不取 $P$ 的答案是 $k$。

• 不选 $A$ 点

那么 $B$ 点和 $C$ 点就都必须选。所以我们可以把两个点还有 $A$ 压成一个点 $P$。此时新图的答案就是 $f[n - 2]$。但是我们多算了一种情况——在新图里不取 $P$ 的情况。这时，我们发现：这种情况的个数恰好就是上文提到的 $k$！

所以答案就非常明显了：

$$f[n] = f[n - 1] + k + f[n - 2] - k = f[n - 1] + f[n - 2]$$

得证万岁！

那么最后还面临着一个小问题——怎么计算连通块里面点的个数。相信大家心里都在默念一个词——并查集！

没错，使用并查集算法求解即可。

AC code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[200010], b[200010];
long long f[200010];
int fa[200010], siz[200010];
int p[200010];
int n;
const int mod = 998244353; //别忘了取模！
void F()
{
	f[1] = 1, f[2] = 3;
	for (int i = 3; i <= n; i++)
		f[i] = (f[i - 1] + f[i - 2]) % mod;
}//计算f[i]
int find(int x)
{
	while (x != fa[x]) x = fa[x];
	return fa[x];
}
void merge(int x, int y)
{
	int fx = find(x), fy = find(y);
	if (fx != fy)
	{
		fa[fx] = fy;
		siz[fy] += siz[fx];
	}
}//并查集基本操作
int main()
{
	cin >> n;
	F();
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		p[a[i]] = i;//标记正面写着a[i]的卡片标号
		siz[i] = 1;
		fa[i] = i;//并查集的初始化
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
		//p[b[i]]和i建边
		merge(i, p[b[i]]);
	}
	long long ans = 1; //乘法原理求答案
	for (int i = 1; i <= n; i++)
		if (i == fa[i])
		{
			ans *= f[siz[i]];
			ans %= mod;
		}
	cout << ans << endl;
	return 0;
}

总结与反思

这个题的思维难度其实还是挺高的，值得被评绿题。关键在于想到建边的操作，然后求 $f[i]$ 的过程其实很简单，但是证明不太好想，后面并查集还是挺明显的。

最后提醒一句：

别忘了取模！！！