简述
Best Theorem 是用来统计有向图中欧拉回路数目的定理
主要内容
记\(t_x\)表示以\(x\)为根的树形图数量（可以用Matrix Tree求解），\(G=\{V,E\}\)，那么有
\[ec(G)=t_x\cdot\prod_{i\in V}(deg_i-1)! \]\(deg_x\)表示\(x\)的度，如果图中有欧拉回路，那么存在\(deg_{(in)x}=deg_{(out)x}\)，所以可以随便选一种来统计。
code
有 \(n\) 个房间，每个房间有若干把钥匙能够打开特定房间的门。
最初你在房间 \(1\)。每当你到达一个房间，你可以选择该房间的一把钥匙，前往该钥匙对应的房间，并将该钥匙丢到垃圾桶中。
你希望最终回到房间 \(1\)，且垃圾桶中有所有的钥匙。
你需要求出方案数，答案对 \(10^6 + 3\) 取模。两组方案不同，当且仅当使用钥匙的顺序不同。
注意，每把钥匙都是不同的。
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long
using namespace std;
namespace Q{
il int rd(){
ri int x=0;ri bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar('-');
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
il int qpow(int a,int b,int p=1e6+3){
ri int as=1;
while(b>0){
if(b&1) as=as*a%p;
a=a*a%p,b>>=1;
}
return as;
}
il int inv(int a,int p=1e6+3){
return qpow(a,p-2,p);
}
} using namespace Q;
cs int N=105,mod=1e6+3;
struct qwq{
int a[N][N];
il void clr(){
memset(a,0,sizeof(a));
}
il int getdet(int n,int p=mod){
ri int as=1,l,iv;
for(ri int i=2;i<=n;++i){
if(!a[i][i]){
for(ri int j=i+1;j<=n;++j){
if(a[j][i]){
swap(a[i],a[j]);
as*=-1;
break;
}
}
}
if(!a[i][i]) continue;
as=as*a[i][i]%p;
iv=inv(a[i][i]);
for(ri int j=i+1;j<=n;++j){
l=a[j][i]*iv%mod;
if(!l) continue;
for(ri int k=i+1;k<=n;++k){
a[j][k]=(a[j][k]-a[i][k]*l%p+p)%p;
}
}
}
return as;
}
}o;
int jc[1<<18|1];
il void init(int n){
jc[0]=1;
for(ri int i=1;i<=n;++i){
jc[i]=jc[i-1]*i%mod;
}
}
int t,n,in[N],out[N],f,T1,cnt;
int b[N];
il int up(int u){
return u==b[u]?u:b[u]=up(b[u]);
}
signed main(){
init(1<<18);
t=rd();
while(t--){
memset(in,0,sizeof(in));
cnt=0;
o.clr();
n=rd();
for(ri int i=1;i<=n;++i) b[i]=i;
for(ri int i=1,v;i<=n;++i){
out[i]=rd();
for(ri int j=1;j<=out[i];++j){
v=rd(),o.a[v][v]++,o.a[i][v]--,in[v]++;
if(o.a[v][v]>=mod) o.a[v][v]-=mod;
if(o.a[i][v]<0) o.a[i][v]+=mod;
b[up(i)]=up(v);
}
}
f=0;
for(ri int i=1;i<=n;++i){
if(in[i]!=out[i]){f=1;break;}
}
if(!f) for(ri int i=1;i<=n;++i){
if(up(i)!=up(1)&&in[i]){f=1;break;}
}
if(f) { puts("0"); continue; }
T1=o.getdet(n)*jc[in[1]]%mod;
//因为起点为 1，所以以 1 为开头的路，是可以循环同构的，而其他的点是不能循环同构
//本质上，原来的best已经把从所有点出发的循环同构算过一遍了，唯独不算从根开始的全局构。
//但现在要求算上，于是最后的结果需要乘上 deg1
for(ri int i=2;i<=n;++i){
if(!in[i]) continue;
T1=T1*jc[in[i]-1]%mod;
if(up(i)==up(1)) f=1;
}
if(f) wt(T1),putchar('\n');
else wt(jc[in[1]]),putchar('\n');
/*
关于 #11 (没错，说的就是我)
大概有这么几个情况吧
-整张图没有边 ans=1 好奇这种情况为什么不是 0
-有没有出入度的无效点 应该忽略掉
-整张图不连通 ans=0
-不存在欧拉路 ans=0
-整张图存在边的情况下一号点的度数为0
*/
}
return 0;
}