[abc262E] red and blue gragh 题解

挺喜欢这道题的，但是因为 vp 时过了不能写成做题笔记，所以只能写成题解了。

绿太配这道题了，实现难度极低，但思维难度较大。AT 评了 #1719，倒也算恰当。

题意：给定一张 \(n\) 点 \(m\) 边的无向图，每个点染成红或蓝，恰 \(k\) 点染红，使得两端点不同色的边的数目为偶数，输出方案数。

两端点不同色，两端点同色，这其实和膜二加法很像。或者说，通过膜二加法区分。

如果把蓝色赋值为 \(0\)，红色赋值为 \(1\)，则一条边的边权为两边点权和膜二。因为边权为奇数的边的数目为偶数，边权和为偶数。

现在从点的视角看问题。每个点对边权和贡献点权与度数的乘积。所以只用看度数为奇数的点。

因此，红色的点中，度数为奇数的点为偶数个。换句话说，度数为奇数的点中，红色的点有偶数个。

枚举几个红色奇数度点，组合数直接算，做完了。

作为近三个月前的 abc，这道题居然有翻译和三十余发提交，说明这道题确实是一道令人印象深刻的好题。

这道题蕴含了一些 MO 组合中常用的思想：赋值、算两次。

事实上，这种奇偶问题，赋值法几乎是最通用的方法。

代码不给了，确实很好写。