首页 > 其他分享 >abc262 E - Red and Blue Graph

abc262 E - Red and Blue Graph

时间:2023-01-10 22:34:52浏览次数:49  
标签:Blue int Graph 度为 偶数 abc262 dg 红点

题意:

对给定无向图进行红蓝2染色,要求红点恰有 \(k\) 个,且两端点异色的边有偶数条。问染色方案数

无重边无自环

\(n\le 2e5\)

思路:

考虑dp -> 复杂度不行。考虑组合数 -> 多半有啥跟度数有关的性质 -> 考虑各种边 -> 没想出来,gg

红点的度数总和 = 红-红边数 × 2 + 红-蓝边数

那么度为奇的红点必须有偶数个。同理度为奇的蓝点必须有偶数个。于是度为奇的点必须有偶数个

不难发现上述条件也是充分的,即只要随便选偶数个奇度点涂红,再在偶度点中涂够 \(k\) 个红点

void sol() {
    int n, m, k; cin >> n >> m >> k;
    vector<int> dg(n + 1);
    while(m--) {
        int x, y; cin >> x >> y;
        dg[x]++, dg[y]++;
    }
    
    int x = 0; //奇度点数
    for(int i = 1; i <= n; i++)
        if(dg[i] % 2) x++;
    if(x % 2) return cout << 0, void();
    ll ans = 0;
    for(int i = 0; i <= x; i += 2)
        (ans += C(x, i) * C(n - x, k - i) % P) %= P;
    cout << (ans + P) % P;
}

标签:Blue,int,Graph,度为,偶数,abc262,dg,红点
From: https://www.cnblogs.com/wushansinger/p/17041552.html

相关文章

  • DevOps实战系列【第十三章】:流水线应用工具Blue Ocean使用
    个人亲自录制全套DevOps系列实战教程:​​手把手教你玩转DevOps全栈技术​​BlueOcean图形化工具可以通过插件的方式安装到jenkins,搜索“BlueOcean”,安装后重启即可。由于......
  • Atcoder Beginner Contest ABC 284 Ex Count Unlabeled Graphs 题解 (Polya定理)
    题目链接弱化版(其实完全一样)u1s1,洛谷上这题的第一个题解写得很不错,可以参考直接边讲Polya定理边做这题问题引入:n颗珠子组成的手串,每颗珠子有两种不同的颜色,如果两......
  • Atcoder Beginner Contest ABC 284 Ex Count Unlabeled Graphs 题解 (Polya定理)
    题目链接弱化版(其实完全一样)u1s1,洛谷上这题的第一个题解写得很不错,可以参考直接边讲Polya定理边做这题问题引入:n颗珠子组成的手串,每颗珠子有两种不同的颜色,如果两......
  • LiMaosen-2022-SkeletonPartedGraphScattering-ECCV
    Skeleton-PartedGraphScatteringNetworksfor3DHumanMotionPrediction#paper1.paper-info1.1MetadataAuthor::[[MaosenLi]],[[SihengChen]],[[Zijing......
  • cartographer 使用自己的雷达
    文件修改demo_revo_lds.launch<!--Copyright2016TheCartographerAuthorsLicensedundertheApacheLicense,Version2.0(the"License");youmaynotu......
  • NC22600 Rinne Loves Dynamic Graph
    题目链接题目题目描述Rinne学到了一个新的奇妙的东西叫做动态图,这里的动态图的定义是边权可以随着操作而变动的图。当我们在这个图上经过一条边的时候,这个图上所有边......
  • NC22594 Rinne Loves Graph
    题目链接题目题目描述Island发生了一场暴乱!现在Rinne要和Setsuna立马到地上世界去。众所周知:Island是有一些奇怪的城镇和道路构成的(题目需要,游戏党勿喷),有些城镇......
  • 读 NebulaGraph源码 | 查询语句 LOOKUP 的一生
    本文由社区用户Milittle供稿LOOKUP是图数据库NebulaGraph的一个查询语句。它依赖索引,可以查询点或者边的信息。在本文,我将着重从源码的角度解析一下LOOKUP语句......
  • Homography|单应性
    文章目录​​几何变换类型​​​​WhatisHomography?​​​​HowtocalculateaHomography?​​​​理论推导​​​​工程实践​​​​Application​​​​Reference​......
  • 建筑软件解决方案丨Bluebeam简介
    BluebeamRevu和BluebeamCloud让团队可以灵活地在任何地方通过设计、构建和移交进行协作。 桌面和云协作解决方案桌面和云协作解决方案基于开放标准构建,因此......