题目传送门: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; }
Comments NOTHING