[ABC262E] Red and Blue Graph 题解

· · 题解

本题解题关键点在于：

连接不同颜色结点的边的数量与红色结点度数之和 \deg_R 的奇偶性相同。这是因为两端均为红色结点的边对 \deg_R 的贡献为偶数（每条贡献 2），而每条异色边对 \deg_R 的贡献为 1。

于是问题改写为：求出具有 K 个红色点，且具有奇数个红色奇度点的图的数量。直接枚举奇度点中有几个是红色的（使用组合数求方案数），最后求和即可。时间复杂度 O(n) 或 O(n\log n)，取决于实现。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5,P=998244353;
static int f[N+1];
int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=r%P*a%P;
    a=a%P*a%P; b>>=1;
  }
  return r;
}
int inv(int a,int b){return a%P*qpow(b,P-2)%P;}
int com(int n,int m){return m?inv(f[n],f[m]*f[n-m]%P):1;}
main(){
  ios::sync_with_stdio(false);
  int n,m,k,c=0,s=0; cin>>n>>m>>k;
  for(int i=f[0]=1;i<=n;i++)
    f[i]=f[i-1]*i%P;
  vector<vector<int> > g(n);
  for(int i=0;i<m;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  for(int i=0;i<n;i++)
    c+=g[i].size()&1; // 统计度为奇数的点的个数
  for(int i=0;i<=min(c,k);i+=2)
    if(k-i<=n-c)(s+=com(c,i)*com(n-c,k-i))%=P; // 枚举数量，用组合数求解
  cout<<s<<endl;
  return 0;
}