bzoj3659: Which Dreamed It

题面在这里

题意：

有n个房间，每个房间有若干把钥匙能够打开某个房间的门。
最初你在房间1。

每当你到达一个房间，你可以选择该房间的一把钥匙，前往该钥匙对应的房间，并将该钥匙丢到垃圾桶中。

你希望最终回到房间1，且垃圾桶中有所有的钥匙。
求方案数。两组方案不同，当且仅当使用钥匙的顺序不同。
每把钥匙都是不同的。
房间数小于等于100，钥匙数小于等于200000.

做法：

我做的都是些啥题啊（雾）感觉自己学了一些奇怪的定理就没啥了

普及一些奇怪的定理。。
best theorem（最好定理？？（雾
有向图中以i为起点的欧拉回路个数为：以i为根的树形图个数×∏i=1n(degi−1)!$以i为根的树形图个数\times \prod _{i=1}^n(de{g}_i-1)!$.
matrix tree theorem（矩阵树定理）
以i为根的树形图个数=基尔霍夫矩阵去掉第i行第i列的行列式.

基尔霍夫矩阵：度数矩阵减去邻接矩阵（邻接矩阵要记录度数）

于是ans=以1为起点的欧拉回路个数×deg1$ans=以1为起点的欧拉回路个数\times de{g}_1$

至于行列式怎么求，就高斯消元一下好了。

代码：

/*************************************************************
    Problem: bzoj 3659 Which Dreamed It
    User: fengyuan
    Language: C++
    Result: Accepted
    Time: 808 ms
    Memory: 2172 kb
    Submit_Time: 2018-01-24 14:50:07
*************************************************************/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cctype>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long ll;

inline ll read() {
    char ch = getchar(); ll x = 0; int op = 1;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') op = -1;
    for(; isdigit(ch); ch = getchar()) x = x*10+ch-'0';
    return x*op;
}
inline void write(ll a) {
    if(a < 0) putchar('-'), a = -a;
    if(a >= 10) write(a/10); putchar('0'+a%10);
}

const int N = 110, M = 200010;
const int mod = 1000003;
int n, m;
int a[N][N], e[N][N], fac[M], vis[N], in[N], out[N];

inline int ksm(int x, int p) {
    int ret = 1;
    for(; p; p >>= 1, x = (ll)x*x%mod) if(p&1) ret = (ll)ret*x%mod;
    return ret;
}
inline int inv(int x) { return ksm(x, mod-2); }
inline void prepare() { fac[0] = 1; for(int i = 1; i < M; i ++) fac[i] = (ll)fac[i-1]*i%mod; }
inline void dfs(int u) {
    vis[u] = ++ m;
    for(int i = 1; i <= n; i ++) if(e[u][i] && !vis[i]) dfs(i);
}
inline int det(int n) {
    int ans = 1; bool flag = 0;
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) a[i][j] = (a[i][j]%mod+mod)%mod;
    for(int i = 1; i <= n; i ++) {
        int r = i;
        for(int j = i+1; j <= n; j ++) if(a[j][i]) { r = j; break; }
        if(i != r) { for(int j = i; j <= n; j ++) swap(a[i][j], a[r][j]); flag ^= 1; }
        int ttt = inv(a[i][i]);
        for(int j = i+1; j <= n; j ++) {
            int t = (ll)a[j][i]*ttt%mod;
            for(int k = i; k <= n; k ++) a[j][k] = (a[j][k]+mod-(ll)t*a[i][k]%mod)%mod;
        }
        ans = (ll)ans*a[i][i]%mod;
        if(!ans) return 0;
    }
    if(flag) ans = (mod-ans)%mod;
    return ans;
}
int main() {
    prepare();
    while(1) {
        n = read(); if(!n) break;
        memset(a, 0, sizeof a); memset(e, 0, sizeof e); memset(vis, 0, sizeof vis);
        memset(in, 0, sizeof in); memset(out, 0, sizeof out);
        for(int i = 1; i <= n; i ++) {
            int k = read();
            while(k --) { int x = read(); e[i][x] ++; }
        } m = 0;
        dfs(1); bool flag = 1;
        for(int i = 1; i <= n; i ++)
            if(!vis[i] && e[i]) { flag = 0; break; }
        if(!flag) { puts("0"); continue; }
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++) if(e[i][j]) {
                int x = vis[i], y = vis[j];//vis[i]是给节点重新编号，剔除不存在的点
                in[y] += e[i][j]; out[x] += e[i][j];
                a[x-1][y-1] = (a[x-1][y-1]-e[i][j]+mod)%mod; a[x-1][x-1] = (a[x-1][x-1]+e[i][j])%mod;
            } flag = 1;
        for(int i = 1; i <= m; i ++) if(in[i] != out[i]) { flag = 0; break; }
        if(!flag) { puts("0"); continue; }
        if(m == 1) { write(fac[e[1][1]]); continue; }
        int ans = (ll)det(m-1)*in[1]%mod;
        for(int i = 1; i <= m; i ++) ans = (ll)ans*fac[in[i]-1]%mod;
        write(ans); puts("");
    } return 0;
}