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-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?