# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### 题解 P5807 【Which Dreamed It】

posted on 2020-02-17 21:09:35 | under 题解 |

Best Theorem 的板子题…

Best Theorem 本质上是用来统计有向图中欧拉回路数目定理。记 $t_x$ 表示以 $x$ 为根的树形图的数量，$G=\{V,E\}$， 那么有

$$\mathrm{ec}(G)= t_x \prod _{i\in V}(\deg_i-1)!$$

upd：

orz JKlover

const int N = 110 ;
const int M = 500010 ;
const int P = 1000003 ;

typedef long long LL ;

int T ;
int n ;
int I[M] ;
int fa[M] ;

LL res ;
LL fac[M] ;
LL deg[M] ;
LL D[N][N] ;
LL K[N][N] ;
LL A[N][N] ;

LL Gauss(){
LL ans = 1 ;
for (int i = 1 ; i < n ; ++ i){
for (int j = i + 1 ; j < n ; ++ j){
while(K[j][i]){
LL t = K[i][i] / K[j][i] ;
for(int k = i ; k < n ; ++ k)
K[i][k] = (K[i][k] - t * K[j][k]) % P ;
swap(K[i], K[j]), ans = (-ans % P + P) % P ;
}
}
if (K[i][i]) (ans *= K[i][i]) %= P ;
}
return (ans % P + P) % P ;
}
void clear(){
memset(K, 0, sizeof(K)) ;
memset(A, 0, sizeof(A)) ;
memset(D, 0, sizeof(D)) ;
memset(I, 0, sizeof(I)) ;
for (int i = 1 ; i <= n ; ++ i) fa[i] = i ;
}
int find_f(int x){
return x == fa[x] ? x : fa[x] = find_f(fa[x]) ;
}
int main(){
cin >> T ; fac[0] = 1 ;
for (LL i = 1 ; i <= 500000 ; ++ i)
fac[i] = fac[i - 1] * i % P ;
while (T --){
scanf("%d", &n) ; clear() ;
for (int i = 1 ; i <= n ; ++ i){
int k, s ; cin >> s ; deg[i] = s ;
for (int j = 1 ; j <= s ; ++ j){
cin >> k ; A[i][k] ++, D[k][k] ++, ++ I[k] ;
if (find_f(i) != find_f(k)) fa[find_f(i)] = find_f(k) ;
}
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; j <= n ; ++ j)
K[i][j] = ((D[i][j] - A[i][j]) % P + P) % P ;
for (int i = 1 ; i <= n ; ++ i)
if (I[i] != deg[i])  goto lalala ;
for (int i = 1 ; i <= n ; ++ i)
if (find_f(i) != find_f(1) && deg[i]) goto lalala ;
res = deg[1] * Gauss() % P ;
for (int i = 1 ; i <= n ; ++ i)
if (deg[i]) (res *= fac[deg[i] - 1]) %= P ;
for (int i = 2 ; i <= n ; ++ i)
if (find_f(i) == find_f(1)) goto lelele ;
cout << fac[deg[1]] << endl ; continue ;
lalala : puts("0") ; continue ;
lelele : cout << res << endl ;
}
return 0 ;
}