【BZOJ4596】【Luogu P4336】 [SHOI2016]黑暗前的幻想乡 矩阵树定理，容斥
2024-09-02 06:25:09
同样是矩阵树定理的裸题。但是要解决它需要能够想到容斥才可以。
\(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 安全验证问题
- 这10道javascript笔试题你都会么
- 2013/11/22工作随笔-缓存是放在Model层还是放在Controller层
- Autolayout及VFL经验分享
- Struts2_ValueStack,OGNL详解
- NSNotification系统通知优化
- 解决在windows的eclipse上面运行WordCount程序出现的一系列问题详解
- Redis 命令 - Transactions
- 百度的TSDB——可针对tag查询，应该类似kairosDB
- req.body取不到值的问题；
- USB接口的SmartCard Class协议标准：ICCD and CCID
- 从源代码上分析ListView的addHeaderView和setAdapter的调用顺序
- 关于linux修改max user processes limits的问题
- headfirst设计模式（3）—装饰者模式
- AOF持久化
- chrome浏览器另存为/上传附件崩溃
- pip Read timed out 和 pip 源
- （玩起来）DAX/PowerBI系列 - 参数表(Parameter Table) - 多时间段数值对比
- BZOJ1087[SCOI2005]互不侵犯——状压DP
- python---RabbitMQ（4）exchange中模糊匹配topic