生成树计数问题总结
其实就是两道裸题,用矩阵树定理行列式求值去做。
矩阵树定理中的邻接矩阵内数字可以是实数,实际上这也就允许了实数边权套用矩阵树定理。
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; } |