ABC262E Red and Blue Graph 做题记录

nnmm 边的无向图里面选 kk 个点,满足与其它 nkn-k 个点之间的连边条数为偶数,求方案数。

提示:考虑节点的度。
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

结论:度为偶数的点可以随便选,度为奇数的点选偶数个。

证明:

  • 度为偶数的点

    1. 若这些点之间没有边相连,结论显然成立。

    2. 否则若 u,vu,v 之间有边相连,显然若都选它们则度数都变为奇数,加起来还是偶数;若只选一个或者不选,则与情况 1 同理。

    3. 若更多的点之间有边相连,那么和情况 2 同理。

  • 度为奇数的点

    1. 若这些点之间没有边相连,结论显然成立。
    2. 否则若 u,vu,v 之间有边相连,显然若都选它们则度数都变为偶数,加起来还是偶数;若只选一个或者不选,则与情况 1 同理。
    3. 若更多的点之间有边相连,那么和情况 2 同理。

证毕。

赛时想了 1h。