对于 \(\sum |E'|\)，直接计算是简单的。
对于 \(\sum |E'|^2\)，拆下贡献，可以拆成 \(\sum\sum_{i,j\in E'}1\)，设 \(U\) 为 \(i\) 和 \(j\) 两条边连接的点集，转化一下式子即为 \(\sum_i\sum_j2^{n-|U|}\)。对于 \(\sum |E'|^3\) 同理，\(U\) 为 \(i,j,k\) 三条边连接的点集，原式即为 \(\sum_i\sum_j\sum_k2^{n-|U|}\)。
于是我们可以对 \(|U|\) 分讨计数：（这里贺一下官方题解）
容斥一下即可，感觉直接给代码比干讲更好理解些
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
#define per(i, x, y) for (int i = (x); i >= (y); i--)
#define int long long
using ll = long long; using ull = unsigned long long;
inline int read() {
char ch = getchar(); int s = 0, f = 1;
while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
constexpr int N = 1e5 + 5, mod = 1e9 + 7;
int n, m, k, pw[N], fac[N], ifac[N], inv[N];
inline int C(int x, int y) {
if (x < y || x < 0 || y < 0) return 0;
return fac[x] * ifac[x - y] % mod * ifac[y] % mod;
}
namespace sub1 {
int f[N], g[N];
inline int sol() {
pw[0] = 1; rep (i, 1, N - 5) pw[i] = pw[i - 1] * 2 % mod;
rep (i, 1, m) {
int u = read(), v = read();
if (u > v) swap(u, v);
(g[v] += pw[v - 2]) %= mod;
}
rep (i, 2, n) {
f[i] = (f[i - 1] * 2 + g[i]) % mod;
} cout << f[n]; return 0;
}
}
namespace sub2 {
int d[N];
inline int sol() {
// |U| = 2
int ans = m * pw[n - 2], cnt = C(m, 2);
while (m--) {
int u = read(), v = read();
d[u]++, d[v]++;
}
// |U| = 3
rep (i, 1, n) {
(ans += C(d[i], 2) * pw[n - 3] * 2) %= mod;
(cnt -= C(d[i], 2)) %= mod;
}
// |U| = 4
(ans += cnt * pw[n - 4] * 2) %= mod;
cout << (ans + mod) % mod;
return 0;
}
}
namespace sub3 {
int d[N], vis[N]; array<int, 2> E[N];
vector<int> e[N];
inline int sol1() {
int res = 0;
rep (i, 1, m) {
int u = E[i][0], v = E[i][1];
if (d[u] > d[v]) swap(u, v);
else if (d[u] == d[v] && u > v) swap(u, v);
e[u].push_back(v);
}
rep (u, 1, n) {
for (auto v : e[u]) vis[v] = u;
for (auto v : e[u]) for (auto w : e[v])
if (vis[w] == u) res++;
} return res;
}
inline int sol() {
int ans = 0, cnt = m * m * m, c2 = C(m, 2), cc = 0, c1 = 0;
rep (i, 1, m) {
int u = read(), v = read();
d[u]++, d[v]++;
E[i] = {u, v};
}
// |U| = 2
(cnt -= m) %= mod, (ans += m * pw[n - 2]) %= mod;
// |U| = 3
int x = sol1();
(ans += x * pw[n - 3] * 6) %= mod;
(cnt -= x * 6) %= mod;
rep (i, 1, n) {
(ans += C(d[i], 2) * pw[n - 3] * 6) %= mod;
(cnt -= C(d[i], 2) * 6) %= mod;
(c2 -= C(d[i], 2)) %= mod;
(cc += C(d[i], 2)) %= mod;
}
// |U| = 4
(ans += c2 * pw[n - 4] * 6) %= mod, (cnt -= c2 * 6) %= mod;
int s = -x * 3;
rep (i, 1, m) {
int u = E[i][0], v = E[i][1];
(s += (d[u] - 1) * (d[v] - 1)) %= mod;
}
(ans += s * pw[n - 4] * 6) %= mod, (cnt -= s * 6) %= mod;
rep (i, 1, n) {
(ans += C(d[i], 3) * pw[n - 4] * 6) %= mod;
(cnt -= C(d[i], 3) * 6) %= mod;
(c1 += C(d[i], 3)) %= mod;
}
// |U| = 5
int y = (cc * (m - 2) - c1 * 3 - s * 2 - x * 3) % mod;
(ans += y * pw[n - 5] * 6) %= mod, (cnt -= y * 6) %= mod;
// |U| = 6
(ans += cnt * pw[n - 6]) %= mod;
cout << (ans + mod) % mod; return 0;
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
n = read(), m = read(), k = read();
pw[0] = fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1; pw[1] = 2;
rep (i, 2, N - 5) {
pw[i] = pw[i - 1] * 2 % mod;
fac[i] = fac[i - 1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
ifac[i] = ifac[i - 1] * inv[i] % mod;
}
if (k == 1) return sub1::sol();
if (k == 2) return sub2::sol();
if (k == 3) return sub3::sol();
return 0;
}