D - Odd Degree¶

题意¶

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。頂点には $1,\ldots,N$ の番号がついています。 $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結んでいます。このグラフの全域部分グラフ(※)であって、次数が奇数の頂点がちょうど $K$ 個であるものの個数をすべての $K$ ( $0≤K≤N$ ) について求めてください。ただし答えは非常に大きくなる可能性があるので、 $998244353$ で割った余りを出力してください。

(※) $G$ の部分グラフ $H$ が $G$ の全域部分グラフであるとは、 $H$ の頂点集合が $G$ の頂点集合と等しく、 $H$ の辺集合が $G$ の辺集合の部分集合であることをいいます。

解析¶

首先，由于每一条边都对应 $2$ 度数，所有点的度数和一定是偶数，即不存在含有奇数个度数为奇数节点的图。

对于一棵树，若指定了哪些点的度数为奇数 (这些点的数量为偶数)，而其他的点度数为偶数，那该树总是存在恰好 $1$ 个满足这样条件的生成子图。因为那些与叶子节点相邻的边是否保留是确定的，计算完它们对非叶节点的影响后将其和叶子结点删去，就可以得到该问题的子问题。

对于一个连通块，保留一个生成树，其余的边任意选，为了得到指定的奇数度数节点集，生成树的选法是唯一的。故一个大小为 $N$ ，包含 $M$ 条边的连通块的包含恰好 $K$ ( $2\mid K$ ) 个奇度数节点的生成子图数为 $2^{M-N+1}\binom{N}{K}$ 。

对于含多个连通块的图，将各个连通块的答案卷积即可。

实现¶

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 5e3 + 19, mod = 998244353;

std::vector<int> operator*(const std::vector<int> &a, const std::vector<int> &b){
    std::vector<int> res(a.size() + b.size() - 1);
    for(int i = 0; i < (int)a.size(); ++i)
        for(int j = 0; j < (int)b.size(); ++j)
            res[i + j] = (res[i + j] + (ll)a[i] * b[j]) % mod;
    return res;
}

int n, m;

int fa[maxn], size[maxn], deg[maxn];
int find(int node){return fa[node] == node ? node : fa[node] = find(fa[node]); }

void exgcd(int a, int b, int &x, int &y){
    if(!b) return (void)(x = 1, y = 0);
    exgcd(b, a % b, y, x), y -= a / b * x;
}

int fact[maxn], ifact[maxn], p2[maxn];
void init(void){
    p2[0] = 1;
    for(int i = 1; i <= m; ++i) p2[i] = (p2[i - 1] + p2[i - 1]) % mod;
    fact[0] = 1;
    for(int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
    exgcd(fact[n], mod, ifact[n], ifact[0]), ifact[n] = (ifact[n] % mod + mod) % mod;
    for(int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
}

inline int binom(int n, int m){
    return (ll)fact[n] * ifact[n - m] % mod * ifact[m] % mod;
}

int main(){
    std::scanf("%d%d", &n, &m);
    std::iota(fa, fa + 1 + n, 0);
    std::fill(size + 1, size + 1 + n, 1);
    init();
    for(int i = 1, u, v; i <= m; ++i){
        std::scanf("%d%d", &u, &v);
        if(find(u) == find(v)) ++deg[find(u)];
        else{
            size[find(v)] += size[find(u)];
            deg[find(v)] += deg[find(u)] + 1;
            fa[find(u)] = find(v);
        }
    }
    std::vector<int> ans(1, 1);
    for(int i = 1; i <= n; ++i)
        if(find(i) == i){
            static std::vector<int> tmp; tmp.clear();
            tmp.resize(size[i] / 2 + 1);
            for(int j = 0; j < (int)tmp.size(); ++j)
                tmp[j] = (ll)binom(size[i], j * 2) * p2[deg[i] - size[i] + 1] % mod;
            ans = ans * tmp;
        }
    for(int i = 0; i <= n; ++i)
        if((i & 1) || (i >> 1) >= (int)ans.size()) std::puts("0");
        else std::printf("%d\n", ans[i >> 1]);
    return 0;
}

来源¶

AtCoder Regular Contest 115 D - Odd Degree

D - Odd Degree¶

题意¶

解析¶

实现¶

来源¶

评论