abc262 E – Red and Blue Graph

题意：

对给定无向图进行红蓝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;
}