Red and Blue Graph(图论,组合计数)
2022/9/10 6:24:33
本文主要是介绍Red and Blue Graph(图论,组合计数),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意
给定一个\(N\)个点\(M\)条边的无向图。
有\(2^N\)种方式将每个节点染成红色或者蓝色。求满足下列条件的染色方案数:
- 恰好有\(K\)个点染成了红色
- 有偶数条边的端点染成了不同颜色
题目链接:https://atcoder.jp/contests/abc262/tasks/abc262_e
数据范围
\(2 \leq N \leq 2 \times 10^5\)
\(1 \leq M \leq 2 \times 10^5\)
\(0 \leq K \leq N\)
思路
考虑染成红色节点的度数和。令\(S\)为红色节点的度数和,\(R\)为两段点都为红色的边数,\(D\)为两段点为不同颜色的边数,则有:\(S = 2R+D\)
由于\(D\)为偶数,因此\(S\)也为偶数。因此有偶数个红色点的度数为奇数。
因此,可以通过枚举红色点中奇度点的个数进行计数。
代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 200010, mod = 998244353; ll n, m, k; ll deg[N]; ll fac[N], infac[N]; ll qmi(ll a, ll b) { ll res = 1; while(b) { if(b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; } void init() { fac[0] = infac[0] = 1; for(int i = 1; i < N; i ++) { fac[i] = fac[i - 1] * i % mod; infac[i] = infac[i - 1] * qmi(i, mod - 2) % mod; } } ll C(ll a, ll b) { return fac[a] * infac[b] % mod * infac[a - b] % mod; } int main() { scanf("%lld%lld%lld", &n, &m, &k); for(int i = 0; i < m; i ++) { int a, b; scanf("%d%d", &a, &b); deg[a] ++, deg[b] ++; } ll odd = 0, even = 0; for(int i = 1; i <= n; i ++) { if(deg[i] % 2) odd ++; else even ++; } init(); ll res = 0; for(int i = 0; i <= k; i += 2) { if(i > odd) break; if(k - i <= even) res = (res + C(odd, i) * C(even, k - i) % mod) % mod; } printf("%lld\n", res); return 0; }
这篇关于Red and Blue Graph(图论,组合计数)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署