壊すとword│E-olv

menu icon

生成树计数问题总结

2016.01.13 19:32 Wed| 33 visits oi_2016| 2016_刷题日常| Text

其实就是两道裸题，用矩阵树定理行列式求值去做。

矩阵树定理中的邻接矩阵内数字可以是实数，实际上这也就允许了实数边权套用矩阵树定理。

BZOJ3534 [Sdoi2014]重建

 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
#include <bits/stdc++.h>
using namespace std;

#define N 55
#define eps 1e-10

int n;
double d[N][N], num = 1;

double det(double d[N][N], int n)
{
    double re = 1;
    for (int i = 1; i <= n; ++i)
    {
        int t = 0;
        for (int j = i; j <= n; ++j)
            if (fabs(d[j][i]) > eps)
                { t = j; break; }
        if (!t) return 0;
        if (t != i) re *= -1;
        for (int j = 1; j <= n; ++j)
            swap(d[i][j], d[t][j]);
        for (int j = i + 1; j <= n; ++j)
            if (fabs(d[j][i]) > eps)
            {
                double temp = d[j][i] / d[i][i];
                for (int k = i; k <= n; ++k)
                    d[j][k] -= temp * d[i][k];
            }
    }
    for (int i = 1; i <= n; ++i)
        re *= d[i][i];
    return re;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            double x;
            scanf("%lf", &x);
            if (i <= j || x < eps) continue;
            if (x == 1) x -= eps;
            num *= 1 - x;
            d[i][j] = d[j][i] = -x / (1 - x);
            d[i][i] -= d[i][j], d[j][j] -= d[j][i];
        }
    cout << fixed << setprecision(10) << num * det(d, n - 1) << endl;
    return 0;
}

UOJ#75 【UR #6】智商锁

听说在 Linux 的机器上，rand() 的最大值是 maxint。

我们生成 1000 个随机图，求出来每一个图的生成树数量。之后两两枚举图，将生成树个数的积放进哈希表里面，之后 meet in middle 玩一玩就好了。

 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;

#define mod 998244353
#define N 1005

vector<pair<int, int> > v[N];
map<int, pair<int, int> > mp;
long double d[13][13];
int n, test, cnt[N];

int power(int a, int b)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % mod;
        a = 1ll * a * a % mod; b >>= 1;
    }
    return re;
}

long double det(long double d[13][13], int n)
{
    long double re = 1;
    for (int i = 1; i <= n; ++i)
    {
        int t = 0;
        for (int j = i; j <= n; ++j)
            if (fabs(d[j][i]) > 1e-15)
                { t = j; break; }
        if (!t) return 0;
        if (t != i) re *= -1;
        for (int j = 1; j <= n; ++j)
            swap(d[i][j], d[t][j]);
        for (int j = i + 1; j <= n; ++j)
            if (fabs(d[j][i]) > 1e-15)
            {
                long double temp = d[j][i] / d[i][i];
                for (int k = i; k <= n; ++k)
                    d[j][k] -= temp * d[i][k];
            }
    }
    for (int i = 1; i <= n; ++i)
        re *= d[i][i];
    return re;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    srand(1701801078);
    for (int i = 1; i <= 1000; ++i)
    {
        memset(d, 0, sizeof d);
        for (int j = 1; j <= 12; ++j)
            for (int k = j + 1; k <= 12; ++k)
                if (1.0 * rand() / 2147483647 < 0.8)
                    d[j][j] += 1, d[k][k] += 1,
                    d[j][k] -= 1, d[k][j] -= 1,
                    v[i].push_back(make_pair(j, k));
        cnt[i] = (long long)(det(d, 11) + 0.5) % mod;
    }
    for (int i = 1; i <= 1000; ++i)
        for (int j = i + 1; j <= 1000; ++j)
            mp[1ll * cnt[i] * cnt[j] % mod] = make_pair(i, j);
    cin >> test;
    while (test--)
    {
        int n = read();
        for (auto i : mp)
        {
            int t = 1ll * n * power(i.first, mod - 2) % mod;
            if (mp.find(t) == mp.end()) continue;
            int a1 = i.second.first, a2 = i.second.second,
                a3 = mp[t].first, a4 = mp[t].second;
            cout << "48 " << v[a1].size() + v[a2].size()
                            + v[a3].size() + v[a4].size() + 3 << endl;
            cout << "12 13\n24 25\n36 37" << endl;
            for (auto j : v[a1])
                cout << j.first << ' ' << j.second << '\n';
            for (auto j : v[a2])
                cout << j.first + 12 << ' ' << j.second + 12 << '\n';
            for (auto j : v[a3])
                cout << j.first + 24 << ' ' << j.second + 24 << '\n';
            for (auto j : v[a4])
                cout << j.first + 36 << ' ' << j.second + 36 << '\n';
            break;
        }
    }
    return 0;
}
Newer