bzoj 4596 [Shoi2016]黑暗前的幻想乡

Contents

Description
Input
Output
- Sample Input
- Sample Output
题解

Description

四年一度的幻想乡大选开始了，最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡，扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪（人类）博丽灵梦和八云紫等人整日高谈所有妖怪平等，幻想乡多元化等等，对于幻想乡目前面临的种种大问题却给不出合适的解决方案。

风间幽香是幻想乡里少有的意识到了问题的严重性的大妖怪。她这次勇敢的站了出来参加幻想乡大选。提出包括在幻想乡边境建墙（并让人类出钱），大力开展基础设施建设挽回失业率等一系列方案，成为了大选年出人意料的黑马并顺利的当上了幻想乡的大统领。

幽香上台以后，第一项措施就是要修建幻想乡的公路。幻想乡有 N 个城市，之间原来没有任何路。幽香向选民承诺要减税，所以她打算只修 N- 1 条路将这些城市连接起来。但是幻想乡有正好 N- 1 个建筑公司，每个建筑公司都想在修路的过程中获得一些好处。

虽然这些建筑公司在选举前没有给幽香钱，幽香还是打算和他们搞好关系，因为她还指望他们帮她建墙。所以她打算让每个建筑公司都负责一条路来修。每个建筑公司都告诉了幽香自己有能力负责修建的路是哪些城市之间的。所以幽香打算选择 N-1 条能够连接幻想乡所有城市的边，然后每条边都交给一个能够负责该边的建筑公司修建，并且每个建筑公司都恰好修一条边。

幽香现在想要知道一共有多少种可能的方案呢？两个方案不同当且仅当它们要么修的边的集合不同，要么边的分配方式不同。

Input

第一行包含一个正整数 N(N<=17)，表示城市个数。
接下来 N-1 行，其中第 i行表示第 i个建筑公司可以修建的路的列表：
以一个非负数mi 开头，表示其可以修建 mi 条路，接下来有mi 对数，
每对数表示一条边的两个端点。其中不会出现重复的边，也不会出现自环。

Output

仅一行一个整数，表示所有可能的方案数对 10^9 + 7 取模的结果。

Sample Input

2 3 2 4 2

5 2 1 3 1 3 2 4 1 4 3

4 2 1 3 2 4 1 4 2

Sample Output

题解

总方案就相当于任意选的方案-1个公司不选的方案+2个公司不选的方案…

那么就可以用搜索来容斥，算方案的时候可以用矩阵树定理来算。

算行列式的时候由于是整数间的运算，那么消元可以通过两行之间的辗转相除来实现。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 20;
const int mod = 1000000007;
struct edge {
int to, next, from;
}e[N * N * N];
int st[N], f[N][N], a[N][N], tot, n, ans, p, x, y;
void add(int x, int y, int i) {
e[++tot].next = st[i];
e[tot].from = x;
e[tot].to = y, st[i] = tot;
}
int solve(int n) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
a[i][j] = f[i][j];
int ans = 1;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j)
while (a[j][i]) {
int t = a[i][i] / a[j][i];
for (int k = i; k <= n; ++k)
a[i][k] = (a[i][k] - (1ll * a[j][k] * t) % mod) % mod;
for (int k = i; k <= n; ++k)
swap(a[i][k], a[j][k]);
ans = -ans;
}
if (!a[i][i]) return 0;
ans = (1ll * ans * a[i][i]) % mod;
}
return ans;
}
void dfs(int now, int cnt) {
if (now == n) {
ans = (ans + ((cnt & 1) ? -1 : 1) * solve(n - 1)) % mod;
return;
}
dfs(now + 1, cnt);
for (int i = st[now]; i; i = e[i].next)
f[e[i].from][e[i].from]--, f[e[i].to][e[i].to]--,
f[e[i].from][e[i].to]++, f[e[i].to][e[i].from]++;
dfs(now + 1, cnt + 1);
for (int i = st[now]; i; i = e[i].next)
f[e[i].from][e[i].from]++, f[e[i].to][e[i].to]++,
f[e[i].from][e[i].to]--, f[e[i].to][e[i].from]--;
}
main() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
scanf("%d", &p);
for (int j = 1; j <= p; ++j)
scanf("%d%d", &x, &y),
add(x, y, i), f[x][x]++, f[y][y]++, 
f[x][y]--, f[y][x]--;
}
dfs(1, 0);
printf("%d\n", (ans + mod) % mod);
}