E - Red and Blue Graph (Combinatorics)

E - Red and Blue Graph(组合数学)

Because it requires an even number of edges of different colors.

Note the number of edges of different colors as$x$,The number of edges that are all red in color is $y$.

Then the sum of the degrees of red points is ：$2y+x=s$

即$x,s$ 奇偶性相同.

而$s$ 的奇偶性,Only depends on the number of red dots with odd degrees.

Therefore, it is enough to enumerate the number of odd degrees in the red point,The rest are chosen in degrees is even.

#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)	//The number of odd degrees must be even
		ans=(ans+C(num[1],i)*C(num[0],k-i))%mod;
	printf("%lld",ans);
 }