Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 262 E問題 Red and Blue Graph

AtCoder ABC ABC262 E問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点 $M$ 辺の単純無向グラフ $G=(V,E)$ が与えられる. ただし,

$V:=\{1,2, \dots, N\}$
$E:=\{U_j V_j \mid j=1,2, \dots, M\}$

である.

この各頂点を赤または青で塗る. 以下を満たすような塗り方は何通りか?

赤で塗られている頂点は $K$ 個
端点が異なる色で塗られている辺は偶数本

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$0 \leq K \leq N$
$1 \leq U_i \lt V_i \leq N$
$G$ は単純無向グラフ

解法

$x_1, x_2, \dots, x_N \in \mathbb{Z}/2 \mathbb{Z}$ を頂点 $i$ を赤で塗るならば $x_i=[1]$ , 青であれば $x_i=[0]$ を割り当てるとする.

辺 $uv \in E$ に対して, 以下は同値である.

頂点 $u$ と頂点 $v$ が異なる色で塗られている.
$x_u+x_v=[0]$

よって, 求めるべきは以下を満たす $x_1, \dots, x_N$ の場合の数である.

$x_i=[1]$ となる $i$ が $K$ 個
$\displaystyle \sum_{uv \in E} (x_u+x_v)=[1]$

ここで, 頂点 $v$ の次数を $\operatorname{deg}(v)$ と書くことにすると,

$\displaystyle \sum_{uv \in E} (x_u+x_v)=\sum_{i=1}^N \operatorname{deg}(i) x_i$

に注意する. このことから, 次数が奇数である頂点の個数を $p$ とすると, 求めるべきは以下と同じである.

互いに区別がつく $p$ 個の黒いボールと $(N-p)$ 個の白いボールがある. ここから合わせて $K$ 個選びだす方法のうち, 黒いボールが偶数個であるような選び方は何通りか?

黒いボールを取り出す方法で場合分けすることにより, 答えは

$\displaystyle \sum_{0 \leq q \leq K \\ q:{\rm even}} \dbinom{p}{q} \dbinom{N-p}{K-q}$

である. これは $0!, 1!, \dots, N!$ を前計算しておくことにより, $O(N+M)$ 時間で求めることができる.