T4 - 洛谷保存站

# 题意

给定一张 $n$ 个节点 $m$ 条边的简单无向图，和一个整数 $k \in [1, 3]$。你需要将每个点黑白染色。令在一种方案中，有 $m$ 条边的两端点都是黑色。求所有方案的 $m^k$ 的和。

# 做法

$m^k$ 很难受。我们可以理解成有 $m$ 条边，你要从中**依次**选择 $k$ 条边的方案数。**选择的边可能相同**。

例如，$(3,3,2)$ 和 $(2, 3, 3)$ 是不同的方案。

也就是说，答案是对于每种染色局面，从该局面中选择 $k$ 条合法边的方案数，之和。

令 $d_u$ 表示 $u$ 的度数。

每层分类讨论均从易到难。

## 1. $k = 1$

最简单的情况。枚举选择的这条边 $(u, v)$，那么节点 $u, v$ 必须染成黑色，其余的 $n - 2$ 个点随意。因此答案为 $m \times 2^{n-2}$。

## 2. $k = 2$

分类讨论选择的这两条边是否相同。

### 2. 1. 两条边相同

与「**1. $k = 1$**」相同。答案为 $m \times 2^{n-2}$。

### 2. 2. 两条边不同

分类讨论是否共点。

#### 2. 2. 1. 两条边共点

即一条长度为 $2$ 的链。

枚举中间点 $u$。与它相邻的点有 $d_u$ 个，选任意两个都能形成链。选择的方案是 $d_u(d_u-1)$。剩下的 $n - 3$ 个点随意。答案为 $\sum_u 2^{n-3}d_u (d_u - 1)$。

#### 2. 2. 2. 两条边不共点

首先求出有多少对边不共点。这里记顺序。

有多少对边不共点，等价于全集减去有多少对边共点。即 $m(m-1) - \sum_u d_u(d_u - 1)$。

除了这两条边的 $4$ 个顶点外，剩下的 $n - 4$ 个点随意。答案为 $2^{n-4} \times (m(m-1) - \sum_u d_u (d_u - 1))$。

## 3. $k=3$

分类讨论这 $3$ 条边是否相同。

### 3. 1. 三条边全部相同

与「**2. 1. 两条边相同**」类似。答案为 $m \times 2^{n-2}$。

### 3. 2. 三条边中，两条边相同，另一条不同

「**2. 2. 两条边不同**」的答案 $\times 3$。

### 3. 3. 三条边互不相同

它 来 了。

#### 3. 3. 1. 三元环

即三条边首尾顺次相接，形成一个三元环。

答案为图中三元环的数量 $\times 3! \times 2^{n-3}$。其中 $\times 3!$ 是选择的顺序，$2^{n-3}$ 表示除了这个三元环上的三个点外，其余点随意选的方案数。

> 题目描述：求无向图中有多少对点 $(x, y, z)$，使得 $(x, y),(y,z),(z,x) \in E$。
>
> 我们将图中所有无向边定向，从度数大的点指向度数小的点。
>
> 枚举 $x$，将所有与 $x$ 相邻的点染色（无向图上的相邻），枚举 $x$ 指向的点 $y$，枚举 $y$ 指向的点 $z$，判断 $z$ 是否染色。
>
> 复杂度是 $\mathcal O(m \sqrt m)$ 的。证明：
>
> > 瓶颈在于枚举 $x \to y \to z$ 的复杂度。
> >
> > - 如果 $d_y \le \sqrt m$：$x \to y$ 的总数是 $m$，$y \to z$ 的总数 $\le d_y$，所以复杂度 $\mathcal O(m \sqrt m)$。
> > - 如果 $d_y > \sqrt m$：显然 $d_x > \sqrt m$。所以 $x$ 的数量 $\le \sqrt m$。而 $y \to z$ 的总数是 $m$，所以复杂度 $\mathcal O(m \sqrt m)$。

#### 3. 3. 2. 菊花树

即 $3$ 条边共用一个端点。

枚举这个端点 $u$。它有 $d_u$ 个相邻的点。答案为：
$$
3! \times 2^{n-4} \times \sum_u \dbinom {d_u}3
$$

#### 3. 3. 3. 一条长度为 $3$ 的链

即 $a-b-c-d$ 且 $a \ne d$。

枚举边 $(b, c)$。$a$ 的取值有 $d_b-1$ 种，$d$ 的取值有 $d_c - 1$ 种。注意这样算会重复计算「**3. 3. 1. 三元环**」$3$ 次（三元环的每条边都会算一次）。

记图中三元环的数量为 $S_{3.3.1.}$。答案为：
$$
3! \times 2^{n-4}\times \left(\sum_{(b,c)\in E}(d_b - 1)(d_c-1)-3 \times S_{3.3.1.}\right)
$$

#### 3. 3. 4. 两条长度分别为 $1, 2$ 的链

枚举长度为 $2$ 的链的中间点 $u$。与 $u$ 相邻的两个点的方案是 $\dbinom {d_u}2$。长度为 $1$ 的链在剩下 $m - d_u$ 条边中任选。

但也不能任选，这样会重复计算「**3. 3. 1. 三元环**」三次和「**3. 3. 3. 一条长度为 $3$ 的链**」两次。原因分别是一个三元环的每条边都会被算一次；一条长 $3$ 的链的两个端点都会被算一次。

记图中三元环数量为 $S_{3.3.1.}$，长 $3$ 的链数量为 $S_{3.3.3.}$。答案为：
$$
3! \times 2^{n-5} \times \left(\sum_u\dbinom{d_u}2(m-d_u) - S_{3.3.1.} - S_{3.3.3.}\right)
$$

#### 3. 3. 5. 三条长度为 $1$ 的链

即三条边两两不共点。

答案是「**3. 3. 三条边互不相同**」减去所有「**3. 3. $x$**」（$x \in [1, 4]$）。

令图中三元环的数量为 $S_{3.3.1.}$，图中菊花树的数量为 $S_{3.3.2}$，图中长度为 $3$ 的链的数量为 $S_{3.3.3.}$，图中长度为 $1, 2$ 的链对数量为 $S_{3.3.4.}$。那么答案为：
$$
3! \times 2^{n-6} \times \left( \dbinom n3 - S_{3.3.1.} - S_{3.3.2.} - S_{3.3.3.} - S_{3.3.4.} \right)
$$

4KB 极品代码：

```cpp
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, P = 1e9 + 7;

int n, m, k;
int d[N];

int h[N], e[N], ne[N], idx;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int fac[N], inv[N];

int C(int n, int m) {
	return n >= m ? 1ll * fac[n] * inv[m] % P * inv[n - m] % P : 0;
}

int fpm(int a, int b) {
	if (b < 0) return 0;
	int res = 1;
	while (b) {
		if (b & 1) res = 1ll * res * a % P;
		b >>= 1, a = 1ll * a * a % P;
	}
	return res;
}

int _21() {
	int res = m % P * fpm(2, n - 2) % P;
	return res;
}

int _221() {
	int res = 0;
	for (int u = 1; u <= n; ++ u ) {
		res = (res + 1ll * d[u] * (d[u] - 1) % P * fpm(2, n - 3) % P) % P;
	}
	return res;
}

int _222() {
	int res = 1ll * m * (m - 1) % P;
	for (int u = 1; u <= n; ++ u ) {
		res = ((res - 1ll * d[u] * (d[u] - 1) % P) % P + P) % P;
	}
	res = 1ll * res * fpm(2, n - 4) % P;
	return res;
}

int _22() {
	int res = (_221() + _222()) % P;
	return res;
}

int _31() {
	int res = 1ll * m * fpm(2, n - 2) % P;
	return res;
}

int _32() {
	int res = 3ll * _22() % P;
	return res;
}

vector<int> g[N];
int st[N];
int A[N], B[N];

int S331, S332, S333, S334;

int _331() {
	int res = 0;
	
	for (int i = 1; i <= m; ++ i ) {
		int a = A[i], b = B[i];
		if (d[a] < d[b] || d[a] == d[b] && a > b) swap(a, b);
		g[a].push_back(b);
	}
	
	for (int x = 1; x <= n; ++ x ) {
		for (int i = h[x]; ~i; i = ne[i]) {
			int z = e[i];
			st[z] = x;
		}
		
		for (int y : g[x])
			for (int z : g[y])
				if (st[z] == x) res ++ ;
	}
	
	S331 = res;
	res = 6ll * res % P * fpm(2, n - 3) % P;
	
	
	return res;
}

int _332() {
	int res = 0;
	for (int u = 1; u <= n; ++ u ) {
		res = (res + C(d[u], 3)) % P;
	}
	S332 = res;
	res = 6ll * res % P * fpm(2, n - 4) % P;
	return res;
}

int _333() {
	int res = 0;
	for (int i = 1; i <= m; ++ i ) {
		int b = A[i], c = B[i];
		res = (res + 1ll * (d[b] - 1) * (d[c] - 1) % P) % P;
	}
	
	res = ((res - 3ll * S331 % P) % P + P) % P;
	S333 = res;
	res = 6ll * res % P * fpm(2, n - 4) % P;
	
	return res;
}

int _334() {
	int res = 0;
	
	for (int u = 1; u <= n; ++ u ) {
		res = (res + 1ll * C(d[u], 2) * (m - d[u]) % P) % P;
	}
	
	res = ((res - 3ll * S331 % P) % P + P) % P;
	res = ((res - 2ll * S333 % P) % P + P) % P;
	S334 = res;
	
	res = 6ll * res % P * fpm(2, n - 5) % P;
	return res;
}

int _335() {
	int res = C(m, 3);
	res = ((res - S331) % P + P) % P;
	res = ((res - S332) % P + P) % P;
	res = ((res - S333) % P + P) % P;
	res = ((res - S334) % P + P) % P;
	res = 6ll * res % P * fpm(2, n - 6) % P;
	return res;
}

int _33() {
	int res = (_331() + _332()) % P;
	res = (res + _333()) % P;
	res = (res + _334()) % P;
	res = (res + _335()) % P;
	return res;
}

signed main() {
	freopen("head.in", "r", stdin);
	freopen("head.out", "w", stdout);
	
	fac[0] = 1;
	for (int i = 1; i < N; ++ i ) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[N - 1] = fpm(fac[N - 1], P - 2);
	for (int i = N - 2; ~i; -- i ) inv[i] = 1ll * inv[i + 1] * (i + 1) % P;
	
	cin >> n >> m >> k;
	
	memset(h, -1, sizeof h);
	for (int i = 1; i <= m; ++ i ) {
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);
		d[a] ++ , d[b] ++ ;
		A[i] = a, B[i] = b;
	}
	
	int res = 0;
	if (k == 1) {
		res = 1ll * m * fpm(2, n - 2) % P;
	}
	else if (k == 2) {
		res = (_21() + _22()) % P;
	}
	else {
		res = ((_31() + _32()) % P + _33()) % P;
	}
	
	cout << res << '\n';
	
	return 0;
}
```

正在渲染内容...