ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[ABC247] F - Card(并查集 + lucas序列)

2022年4月12日 1267点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ lucas 图论 并查集 排列 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号