DDOSvoid's Blog

Luogu P4336 [SHOI2016]黑暗前的幻想乡

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4336

简要题意：现在有 $n$ 个城市，有 $n-1$ 个公司来修路，每个公司可以修某些路，现在要求恰好修 $n-1$ 条路使这 $n$ 个城市连通并且每个公司恰好其中一条路的方案数

$n\le 17$

Solution

我们考虑枚举这次负责修路的公司 $S$，然后用矩阵树定理算出总的方案数 $f_{S}$，令 $g_{S}$ 表示 $S$ 中的每个公司都至少修了一条路的方案数，容易得到 $f_{S}=\sum_{T\subseteq S} g_T$，根据子集反演，可以得到 $g_S=\sum_{T\subseteq S}(-1)^{|S|-|T|}$

因为恰好有 $n-1$ 个公司，所以答案就是 $g_U$，$U$ 表示这 $n-1$ 个公司的集合

时间复杂度 $O(2^nn^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#define maxn 310
#define ll long long
using namespace std;

const int p = 1000000007;
ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

ll g[maxn][maxn];
int Gauss(int n) {
    ll res = 1; 
    for (int i = 1; i <= n; ++i) {
        int pos = -1;
        for (int j = i; j <= n; ++j) if (g[j][i]) pos = j;
        if (pos == -1) return 0; swap(g[i], g[pos]); res *= pos == i ? 1 : -1;
        res = res * g[i][i] % p; ll inv = pow_mod(g[i][i], p - 2);
        for (int j = i + 1; j <= n; ++j) 
            for (int k = n; k >= i; --k)
                g[j][k] = (g[j][k] - g[j][i] * inv % p * g[i][k]) % p;
    } return res;
}

int n;
vector<pair<int, int>> a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; 
    for (int i = 1; i < n; ++i) {
        int len, x, y; cin >> len;
        for (int j = 1; j <= len; ++j) cin >> x >> y, a[i].emplace_back(x, y);
    } int M = (1 << n - 1) - 1; ll ans = 0; 
    for (int S = 0; S <= M; ++S) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) g[i][j] = 0; 
        for (int o = 1; o < n; ++o)
            if (S >> o - 1 & 1) 
                for (auto [x, y] : a[o])
                    --g[x][y], --g[y][x], ++g[x][x], ++g[y][y];
        int cnt = __builtin_popcount(S); ll res = Gauss(n - 1); 
        if (n - 1 - cnt & 1) ans = (ans - res) % p;
        else ans = (ans + res) % p; 
    } cout << (ans + p) % p << "\n";
    return 0;
}