若连通块是一棵树,考虑钦定 \(k\) 个点为奇度点,方案数为 \(\binom{n}{k}\)。对于叶子,如果它是奇度点,那么连向它父亲的边要保留,否则不保留。这样自底向上考虑,任意一条边的保留情况都可以唯一确定,所以最后方案数就是 \(\binom{n}{k}\)。
若连通块存在环,仍然钦定 \(k\) 个点为奇度点。考虑随便拎出一棵生成树,非树边选可不选;确定了非树边的状态,就和树的情况一样了。设连通块边数为 \(m\),最后方案数就是 \(2^{m-n+1} \binom{n}{k}\)。
多个连通块的情况,考虑背包 dp,设 \(f_{i,j}\) 为前 \(i\) 个连通块,选了 \(j\) 个奇度点的方案数。转移枚举第 \(i\) 个连通块钦定 \(k\) 个奇度点(\(k\) 为偶数)即可。
时间复杂度 \(O(n^2)\)。
code
// Problem: D - Odd Degree
// Contest: AtCoder - AtCoder Regular Contest 115
// URL: https://atcoder.jp/contests/arc115/tasks/arc115_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 5050;
const int N = 5000;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
int n, m, a[maxn], sz[maxn], fa[maxn];
ll fac[maxn], ifac[maxn], pw[maxn], f[maxn][maxn];
pii E[maxn];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
sz[y] += sz[x];
}
}
void init() {
pw[0] = fac[0] = 1;
for (int i = 1; i <= N; ++i) {
pw[i] = pw[i - 1] * 2 % mod;
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
fa[i] = i;
sz[i] = 1;
}
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &E[i].fst, &E[i].scd);
merge(E[i].fst, E[i].scd);
}
for (int i = 1; i <= m; ++i) {
++a[find(E[i].fst)];
}
f[0][0] = 1;
int t = 0;
for (int i = 1; i <= n; ++i) {
if (fa[i] != i) {
continue;
}
++t;
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= min(sz[i], j); k += 2) {
f[t][j] = (f[t][j] + f[t - 1][j - k] * C(sz[i], k) % mod * pw[a[i] - (sz[i] - 1)] % mod) % mod;
}
}
}
for (int i = 0; i <= n; ++i) {
printf("%lld\n", f[t][i]);
}
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Regular Contest Degree 115atcoder regular contest degree atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest inversion atcoder regular contest