[BZOJ4596][Shoi2016]黑暗前的幻想鄉（容斥+矩陣樹定理）

Description

四年一度的幻想鄉大選開始了，最近幻想鄉最大的問題是很多來曆不明的妖怪湧入了幻想鄉，擾亂了幻想鄉昔日的秩序。但是幻想鄉的建制派妖怪（人類）博麗靈夢和八雲紫等人整日高談所有妖怪平等，幻想鄉多元化等等，對于幻想鄉目前面臨的種種大問題卻給不出合适的解決方案。

風間幽香是幻想鄉裡少有的意識到了問題的嚴重性的大妖怪。她這次勇敢的站了出來參加幻想鄉大選。提出包括在幻想鄉邊境建牆（并讓人類出錢），大力

開展基礎設施建設挽回失業率等一系列方案，成為了大選年出人意料的黑馬并順

利的當上了幻想鄉的大統領。

幽香上台以後，第一項措施就是要修建幻想鄉的公路。幻想鄉有 N N 個城市，之間原來沒有任何路。幽香向選民承諾要減稅，是以她打算隻修 N−1N−1 條路将這些城市連接配接起來。但是幻想鄉有正好 N−1 N − 1 個建築公司，每個建築公司都想在修路的過程中獲得一些好處。

雖然這些建築公司在選舉前沒有給幽香錢，幽香還是打算和他們搞好關系，因為她還指望他們幫她建牆。是以她打算讓每個建築公司都負責一條路來修。

每個建築公司都告訴了幽香自己有能力負責修建的路是哪些城市之間的。是以幽香打算選擇 N−1 N − 1 條能夠連接配接幻想鄉所有城市的邊，然後每條邊都交給一個能夠負責該邊的建築公司修建，并且每個建築公司都恰好修一條邊。

幽香現在想要知道一共有多少種可能的方案呢？兩個方案不同當且僅當它們要麼修的邊的集合不同，要麼邊的配置設定方式不同。

Input

第一行包含一個正整數 N(N≤17) N ( N ≤ 17 ) ，表示城市個數。

接下來 N−1 N − 1 行，其中第 i i 行表示第 ii 個建築公司可以修建的路的清單：

以一個非負數 mi m i 開頭，表示其可以修建 mi m i 條路，接下來有 mi m i 對數，

每對數表示一條邊的兩個端點。其中不會出現重複的邊，也不會出現自環。

Output

僅一行一個整數，表示所有可能的方案數對 109+7 10 9 + 7 取模的結果。

Sample Input

4

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

17

Solution

顯然是一個生成樹計數問題。

但生成樹中選出的邊是有限制的：給定 n−1 n − 1 組邊，規定每條邊都必須選每一組邊中的一條。

于是就考慮容斥：

2n−1 2 n − 1 暴力枚舉 {1,2,...,n−1} { 1 , 2 , . . . , n − 1 } 的一個子集 S S ，并強制 SS 内的元素對應的邊集不能被作為生成樹上的邊，每次求一遍生成樹個數。

這樣，答案就為：

|S|=0的生成樹個數−|S|=1的生成樹個數+|S|=2的生成樹個數−... | S | = 0 的 生 成 樹 個 數 − | S | = 1 的 生 成 樹 個 數 + | S | = 2 的 生 成 樹 個 數 − . . .

求生成樹個數，可以用 Matrix-Tree 矩陣樹定理求得。

複雜度 O(2nn3log) O ( 2 n n 3 log ) 。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N = , M = N * N, PYZ =  + ;
int n, p[N][M], q[N][M], ans, mat[N][N];
bool sel[N];
int det(int n) {
    int i, j, k; bool op = ;
    For (i, , n) For (j, , n) if (mat[i][j] < ) mat[i][j] += PYZ;
    For (i, , n) For (j, i + , n) {
        int a = mat[i][i], b = mat[j][i]; while (b) {
            int tmp = a / b; a %= b; swap(a, b);
            For (k, i, n) mat[i][k] = (mat[i][k] - l * tmp * mat[j][k]
                % PYZ + PYZ) % PYZ;
            For (k, i, n) swap(mat[i][k], mat[j][k]); op ^= ;
        }
    }
    int ans = ; For (i, , n) ans = l * ans * mat[i][i] % PYZ;
    return op ? (PYZ - ans) % PYZ : ans;
}
void calc(int cnt) {
    int i, j; For (i, , n) For (j, , n) mat[i][j] = ;
    For (i, , n - ) if (sel[i]) For (j, , p[i][])
        mat[p[i][j]][q[i][j]]--, mat[q[i][j]][p[i][j]]--;
    For (i, , n) For (j, , n) if (i != j) mat[i][i] -= mat[i][j];
    int res = det(n - ); if (cnt & ) ans = (ans - res + PYZ) % PYZ;
    else ans = (ans + res) % PYZ;
}
void dfs(int dep, int cnt) {
    if (dep == n) return calc(cnt);
    sel[dep] = ; dfs(dep + , cnt);
    sel[dep] = ; dfs(dep + , cnt + );
}
int main() {
    int i, j; n = read(); For (i, , n - ) {
        p[i][] = read(); For (j, , p[i][]) p[i][j] = read(), q[i][j] = read();
    }
    dfs(, ); cout << ans << endl; return ;
}