QOJ #7324. Eulerian Orientation 题解

Description

众所周知，一个无向图是欧拉图，当且仅当它的每个顶点的度数都是偶数。

现在，Yuuka 有一张包含 $n$ 个顶点、$m$ 条边的无向图，顶点方便地编号为 $1, 2, \dots, n$。所有的边一开始都是蓝色的。Yuuka 计划把其中一些边涂成红色，剩下的保持蓝色。

如果由红色边构成的子图是欧拉图，那么她会将 $x^2$ 加到计数器中，其中 $x$ 是红色边的数量。

她会考虑所有 $2^m$ 种将边涂色的方式，并将这些方式对应的计数器值全部加总。Yuuka 想知道，这个总和对 $(10^9+7)$ 取模的结果。

$n,m\leq 2\times 10^5$。

Solution

首先求 $x^2$ 有个经典的套路是枚举两个边计算这两个边同时出现的次数。

先枚举边并将这两条边删掉，并给这两条边的两个端点分别异或 $1$，如果剩下的每个连通块分别的异或和都是 $0$，答案就是 $2^{m-n+c}$，其中 $c$ 是连通块数量，证明就考虑任意一种非树边选法都唯一对应一个答案。

容易发现只要选的两条边都不是树上的割边就能满足连通块异或和的条件。

现在问题变为求出有多少对边删掉后会使连通块数增加 $1$。

这是个经典的结论，在这里连通块数增加 $1$ 当且仅当两个树边所被覆盖的非树边集合相同，或者一个树边一个非树边，且这个树边只被这个非树边覆盖。

还需要分讨一下重边的情况。

时间复杂度：$O(n+m)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using u64 = uint64_t;

const int kMaxN = 2e5 + 5, kMod = 1e9 + 7;

int n, m, c, cnte, cnt[2];
int u[kMaxN], v[kMaxN], dep[kMaxN], low[kMaxN];
u64 hs[kMaxN];
bool ont[kMaxN];
std::vector<std::pair<int, int>> G[kMaxN];
std::unordered_map<u64, int> mp;
std::mt19937_64 rnd(std::random_device{}());

int qpow(int bs, int64_t idx = kMod - 2) {
  if (idx < 0) return 0;
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void clear() {
  mp.clear();
  for (int i = 1; i <= n; ++i) dep[i] = hs[i] = low[i] = 0, G[i].clear();
  for (int i = 1; i <= m; ++i) ont[i] = 0;
}

void dfs1(int u, int fa) {
  low[u] = dep[u];
  for (auto [v, id] : G[u]) {
    if (id == fa) continue;
    if (!dep[v]) {
      ont[id] = 1, dep[v] = dep[u] + 1, dfs1(v, id);
      low[u] = std::min(low[u], low[v]);
      if (low[v] <= dep[u]) ++cnte;
    } else if (dep[u] <= dep[v]) {
      u64 val = rnd();
      ++mp[val];
      hs[u] ^= val, hs[v] ^= val, ++cnte;
    }
    low[u] = std::min(low[u], dep[v]);
  }
}

void dfs2(int u, int fa) {
  for (auto [v, id] : G[u]) {
    if (id == fa || !ont[id]) continue;
    dfs2(v, id);
    hs[u] ^= hs[v];
  }
  if (low[u] < dep[u]) inc(cnt[1], 2 * (mp[hs[u]]++));
}

void dickdreamer() {
  clear();
  for (int i = 1; i <= m; ++i) {
    std::cin >> u[i] >> v[i];
    G[u[i]].emplace_back(v[i], i);
    if (u[i] != v[i]) G[v[i]].emplace_back(u[i], i);
  }
  c = cnte = cnt[0] = cnt[1] = 0;
  for (int i = 1; i <= n; ++i) {
    if (!dep[i]) {
      ++c, dep[i] = 1, dfs1(i, 0), dfs2(i, 0);
    }
  }
  int tot = 1ll * cnte * (cnte - 1) % kMod;
  cnt[0] = sub(tot, cnt[1]);
  int ans = 0;
  // std::cerr << c << ' ' << cnt[0] << ' ' << cnt[1] << '\n';
  inc(ans, 1ll * cnt[0] * qpow(2, m - 2 - n + c) % kMod);
  inc(ans, 1ll * cnt[1] * qpow(2, m - 2 - n + c + 1) % kMod);
  inc(ans, 1ll * cnte * qpow(2, m - 1 - n + c) % kMod);
  std::cout << ans << '\n';
  // std::cerr << cnte << ' ' << cnt[0] << ' ' << cnt[1] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (std::cin >> n >> m) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}