[ABC247] F - Card（并查集 + lucas序列）

题目传送门：F - Cards (atcoder.jp)

题目大意

给定N张牌，每张牌有两个数字Pi和Qi，所有的牌中P和Q构成两个[1, N]的排列。现在从N张牌中选出任意张牌，请问有多少种选法，使得选出的牌拥有所有[1, N]的数字。

思路

这题看视频吧，有点繁琐不好写。

[AtCoder Beginner Contest 247]简单易懂 A - F算法竞赛刷题记录_哔哩哔哩_bilibili

代码

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int maxn = 2e5 + 9, p = 998244353;

int P[maxn], Q[maxn], pre[maxn], c[maxn], f[maxn];

int root(int x){return pre[x] == x ? x : pre[x] = root(pre[x]);}

signed main()
{
	int N;cin >> N;
	for(int i = 1;i <= N; ++ i)
	{
		scanf("%lld",P + i);
		pre[i] = i;
	}
	for(int i = 1;i <= N; ++ i)
	{
		scanf("%lld",Q + i);
		pre[root(Q[i])] = root(P[i]);
	}
	f[1] = 1,f[2] = 3;
	for(int i = 3;i <= N; ++ i)f[i] = (f[i - 1] + f[i - 2]) % p;
	vector<int> v;
	for(int i = 1;i <= N; ++ i)
	{
		c[root(i)] ++;
		if(root(i) == i)v.push_back(i);
	}
	int ans = 1;
	for(auto &i : v)ans = ans * f[c[i]] % p;
	cout << ans << '\n';
	return 0;
}