当前位置:网站首页>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);
}
边栏推荐
猜你喜欢
随机推荐
SQL函数 SQUARE
LeetCode_位运算_简单_405.数字转换为十六进制数
shell 中的 分发系统 expect脚本 (传递参数、自动同步文件、指定host和要传输的文件、(构建文件分发系统)(命令批量执行))
快速理解拉格朗日乘子法
CCS软件安装教程(超级详细)「建议收藏」
mysql的基本使用
SAP ABAP OData 服务如何支持创建(Create)操作试读版
SQL functions STR
【每日一题】1161. 最大层内元素和
如何将第三方服务中心注册集成到 Istio ?
What Can Service Mesh Learn from SDN?
Programmer's Romantic Tanabata
使用open3d可视化3d人脸
多线程案例——阻塞式队列
力扣160题,相交链表
kubernetes之DaemonSet以及滚动更新
Grafana9.0发布,Prometheus和Loki查询生成器、全新导航、热图面板等新功能!
树和二叉树的转换
数据湖 delta lake和spark版本对应关系
制售假劣农资、非法占用耕地……公安部公布十起危害粮食生产安全犯罪典型案例