题意:
对给定无向图进行红蓝2染色,要求红点恰有 \(k\) 个,且两端点异色的边有偶数条。问染色方案数
无重边无自环
\(n\le 2e5\)
思路:
考虑dp -> 复杂度不行。考虑组合数 -> 多半有啥跟度数有关的性质 -> 考虑各种边 -> 没想出来,gg
红点的度数总和 = 红-红
边数 × 2 + 红-蓝
边数
那么度为奇的红点必须有偶数个。同理度为奇的蓝点必须有偶数个。于是度为奇的点必须有偶数个
不难发现上述条件也是充分的,即只要随便选偶数个奇度点涂红,再在偶度点中涂够 \(k\) 个红点
void sol() {
int n, m, k; cin >> n >> m >> k;
vector<int> dg(n + 1);
while(m--) {
int x, y; cin >> x >> y;
dg[x]++, dg[y]++;
}
int x = 0; //奇度点数
for(int i = 1; i <= n; i++)
if(dg[i] % 2) x++;
if(x % 2) return cout << 0, void();
ll ans = 0;
for(int i = 0; i <= x; i += 2)
(ans += C(x, i) * C(n - x, k - i) % P) %= P;
cout << (ans + P) % P;
}
标签:Blue,int,Graph,度为,偶数,abc262,dg,红点
From: https://www.cnblogs.com/wushansinger/p/17041552.html