T4

2huk · 2024-08-25 17:22:02 · 个人记录

题意

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

做法

最简单的情况。枚举选择的这条边 (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. 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. 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. 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.}。那么答案为：

4KB 极品代码：

#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;
}