当前位置:网站首页>E - Red and Blue Graph(组合数学)
E - Red and Blue Graph(组合数学)
2022-08-01 13:22:00 【Harris-H】
E - Red and Blue Graph(组合数学)
因为要求有偶数个不同颜色的边。
记不同颜色的边个数为 x x x,颜色全为红色的边个数为 y y y。
则红色的点度数之和为: 2 y + x = s 2y+x=s 2y+x=s
即 x , s x,s x,s 奇偶性相同。
而 s s s 的奇偶性,只取决于度数为奇数的红点个数。
因此枚举红色点中度数为奇数的个数即可,剩下在度数为偶数里选。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const ll mod=998244353;
int n,m,k,d[N],num[2];ll inv[N],fac[N],ans;
ll C(int n,int m)
{
if(n<m||m<0) return 0ll;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
for(int i=1,u,v;i<=m;i++)
scanf("%d %d",&u,&v),d[u]++,d[v]++;
fac[0]=inv[1]=inv[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=n;i++) inv[i]=inv[i]*inv[i-1]%mod;
for(int i=1;i<=n;i++)
num[d[i]&1]++;
for(int i=0;i<=num[1];i+=2) //度数为奇数的个数必须为偶数个
ans=(ans+C(num[1],i)*C(num[0],k-i))%mod;
printf("%lld",ans);
}
边栏推荐
猜你喜欢
快速幂---学习笔记
台积电认清了形势,新的建厂计划没有美国,中国芯片也得到重视
预防和制止家庭暴力 人身安全保护令司法解释今起施行
【每日一题】1331. 数组序号转换
消息中间件解析 | 如何正确理解软件应用系统中关于系统通信的那些事?
10年稳定性保障经验总结,故障复盘要回答哪三大关键问题?|TakinTalks大咖分享
HMS Core音频编辑服务音源分离与空间音频渲染,助力快速进入3D音频的世界
The basic knowledge of scripting language Lua summary
全球都热炸了,谷歌服务器已经崩掉了
芝加哥丰田技术学院 | Leveraging Natural Supervision for Language Representation Learning and Generation(利用自然监督进行语言表示学习和生成)
随机推荐
iframe标签属性说明 详解[通俗易懂]
PanGu-Coder:函数级的代码生成模型
Programmer's Romantic Tanabata
PanGu-Coder:函数级的代码生成模型
AD单片机九齐单片机NY8B062D SOP16九齐
Qt实战案例(56)——利用QProcess实现应用程序重启功能
全链路灰度在数据库上我们是怎么做的?
2022-07-25 网工进阶(二十一)BGP-路由反射器、联盟、聚合
魔众短链接系统 v3.9.0
【每日一题】593. 有效的正方形
【码蹄集新手村600题】判断一个数字是否为完全平方数
软件测试之发现和解决bug
AI目标分割能力,无需绿幕即可实现快速视频抠图
Simulation implementation of new of Js handwritten function
postgresql之page分配管理(二)
计算器:中缀表达式转后缀表达式
Why does the maximum plus one equal the minimum
观察者模式
【每日一题】1331. 数组序号转换
formatdatetime函数 mysql(date sub函数)