QOJ #7324. Eulerian Orientation 题解

QOJ #7324. Eulerian Orientation 题解

感觉比较牛的题，可能是我比较菜，学习了官解才学会。
题意

对于一个有 \(n\) 个顶点、\(m\) 条边的无向图，考虑所有 \(2^m\) 种给边染色（红/蓝）的方案。对于每种方案，如果红色边构成的子图是欧拉图（即每个顶点的度数都是偶数），那么就将红色边的数量 \(x\) 的平方加到计数器上。最后输出所有方案的总和模 \(10^9+7\)。
做法

题目其实让求的就是

\[\sum_{F \subseteq E} [F \text{ 是欧拉子图}] \cdot |F|^2\]
其中 \(|F|\) 是红色边的数量。

\[|F|^2 = \left(\sum_{e \in E} [e \in F]\right)^2 = \sum_{e \in E}\sum_{f \in E} [e \in F][f \in F]\]
总和就变成：

\[\sum_{e \in E}\sum_{f \in E} \sum_{F \subseteq E} [F \text{ 是欧拉子图} \land e \in F \land f \in F]\]
交换一下求和顺序就变成：

\[\sum_{e \in E}\sum_{f \in E} (\text{包含 } e \text{ 和 } f \text{ 的欧拉子图数量})\]
好的，问题变成怎么求一个图的欧拉子图数量？
考虑对于一棵树，他的欧拉子图个数是 \(1\)，也就是空集，这个比较显然。
我们考虑加上一条非树边。

此时发现会多一个环，变成两个欧拉子图。
再加一条呢？

此时就会有 \(4\) 个欧拉子图。
好的，我们发现规律了。
对于一个连通图来说，他的欧拉子图个数为 \(2^{m-n+1}\) 个。
非连通图的欧拉子图个数为 \(2^{m-n+c}\) 个
考虑证明：
直观来看，每加一条非树边就会使树上加一个新环，这个环是确定的，我们称他会增加一个自由度。
所以可以选择或者不选择这条非树边，有两种方案。每选择一条非树边都有且确认了欧拉图。
好的，证完了。
然后我们开始分讨上式中的 \(e\) 和 \(f\)。

• 当 \(e = f\) 的时候我们要求必须选 \(e/f\) 这一条边，减少一个自由度，答案为 \(2^{m-n+c-1}\)。
  
• 当 \(e \neq f\) 且 \(\left\{e, f\right\}\) 不是割集，强制选这两个边只会减少两个自由度。
  
• 等 \(e \neq f\) 且 \(\left\{e, f\right\}\) 是割集，此时 \(e\) 和 \(f\) 在同一个环上，他俩会同时选，强制选他只会使自由度减少一。
  

合并一下结果：
令：

• \(d = m - n + c\)
  
• \(k =\) 非割边的数量（即环上的边）
  
• \(X =\) 构成割集的无序对 \(\{e,f\}\) 的数量
  

那么：

• \(e = f\) 的情况贡献：\(m \cdot 2^{d-1}\)
  
• \(e \neq f\) 的情况：
  
  
  
  • 非割集对 \((e,f)\) 的数量 \(= k(k-1) - 2X\)
    
  • 这些对贡献：\(2^{d-2}\)
    
  • 割集对 \((e,f)\) 的数量 \(= X\)
    
  • 这些对贡献：\(2^{d-1}\)
    
  
  

总结果：

\[\begin{aligned}\text{总和} &= m \cdot 2^{d-1} + (k(k-1)-2X) \cdot 2^{d-2} + X \cdot 2^{d-1} \\&= 2^{d-2}[2m + k(k-1)] \\&= 2^{d-2}\left[m + \frac{k(k-1)}{2} + X\right]\end{aligned}\]
剩下就是怎么求 \(X\) 了。
jiangly 给出的方法：

• 给每条非树边随机一个权值
  
• 树边的权值设为覆盖它的所有非树边权值的异或
  
• 性质：\(\{e,f\}\) 是割集当且仅当 \(\text{val}[e] = \text{val}[f]\)
  

什么叫做一个树边被一个非树边覆盖呢：这个非树边和这个树边在同一个环上。
好了，剩下的就是代码了，我实在懒得写了，让 AI 写的嘻嘻。
[code]#include using namespace std;using ll = long long;using ull = unsigned long long;const int MOD = 1e9 + 7;const int MAXN = 200005;const int MAXM = 200005;int n, m;vector adj[MAXN];  // (to, edge id)int u[MAXM], v[MAXM];ull edge_val[MAXM];bool vis[MAXN];int depth[MAXN];ull xor_sum[MAXN];int parent[MAXN], pe[MAXN];  // parent vertex and parent edge idint iter[MAXN];              // current index in adjacency listmt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());ull rand64() {    return rng();}void solve() {    // input edges    for (int i = 0; i < m; ++i) {        cin >> u >> v;        adj[u].emplace_back(v, i);        adj[v].emplace_back(u, i);    }    // initialize    for (int i = 1; i  m) {        solve();        // clear adjacency for next test case        for (int i = 1; i