【BZOJ4596】【Luogu P4336】 [SHOI2016]黑暗前的幻想乡矩阵树定理，容斥

素颜马尾好姑娘i 2022-01-06 12:09 168阅读 0赞

同样是矩阵树定理的裸题。但是要解决它需要能够想到容斥才可以。

**\\(20\\)以内的数据范围一定要试试容斥的想法。**

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 17 + 5; const int mod = 1000000007; int n, k, mat[N][N]; vector <int> u[N], v[N]; int gauss (int n) { int ret = 1; for (int i = 1; i <= n; ++i) { for (int k = i + 1; k <= n; ++k) { while (mat[k][i]) { int d = mat[i][i] / mat[k][i]; for (int j = i; j <= n; ++j) { mat[i][j] = (((mat[i][j] - d * mat[k][j]) % mod) + mod) % mod; } swap (mat[k], mat[i]); ret = -ret; } } ret = (((ret * mat[i][i]) % mod) + mod) % mod; } return ret; } int solve (int sit) { memset (mat, 0, sizeof (mat)); for (int i = 0; i < n - 1; ++i) { if ((sit & (1 << i)) == 0) { // 本位可用 for (int k = 0; k < u[i].size (); ++k) { mat[u[i][k]][u[i][k]]++; mat[v[i][k]][v[i][k]]++; mat[u[i][k]][v[i][k]]--; mat[v[i][k]][u[i][k]]--; } } } return gauss (n - 1); } signed main () { cin >> n; for (int i = 0; i < n - 1; ++i) { cin >> k; for (int j = 0; j < k; ++j) { static int _u, _v; cin >> _u >> _v; u[i].push_back (_u); v[i].push_back (_v); } } int ans = solve (0); // 不考虑有公司不参与的情况 // 某一位为 0 : 可用 // 某一位为 1 : 不可用 int S = (1 << (n - 1)) - 1; for (int S0 = S; S0; S0 = S & (S0 - 1)) { int cnt = 0, _S0 = S0; while (_S0) { cnt++; _S0 -= (_S0 & -_S0); } if (cnt % 2 == 1) { ans = (((ans - solve (S0)) % mod) + mod) % mod; } else { ans = (((ans + solve (S0)) % mod) + mod) % mod; } } cout << ans << endl; }

转载于:https://www.cnblogs.com/maomao9173/p/10944059.html