【模板】BEST 定理 | Which Dreamed It
题目描述
有 $n$ 个房间,每个房间有若干把钥匙能够打开特定房间的门。
最初你在房间 $1$。每当你到达一个房间,你可以选择该房间的一把钥匙,前往该钥匙对应的房间,并将该钥匙丢到垃圾桶中。
你希望最终回到房间 $1$,且垃圾桶中有所有的钥匙。
你需要求出方案数,答案对 $10^6 + 3$ 取模。两组方案不同,当且仅当使用钥匙的顺序不同。
注意,每把钥匙都是不同的。
原 BZOJ3659。
输入输出格式
输入格式
**本题有多组数据。**
第一行一个整数 $T$,表示数据组数。
对于每组数据:
第一行一个整数 $n$。
接下来 $n$ 行,第 $i$ 行描述房间 $i$:
首先一个数 $s$,表示这个房间的钥匙数目,接下来 $s$ 个数,分别描述每把钥匙能够打开的房间的门。
输出格式
对于每组数据,一行一个整数,表示答案对 $10^6+3$ 取模后的值。
输入输出样例
输入样例 #1
2
1
0
2
1 1
1 2
输出样例 #1
1
0
说明
【样例说明】
在第一组样例中,没有钥匙,则方案数为 $1$。
在第二组样例中,你不可能使用第二个房间的钥匙,所以方案数为 $0$。
【数据范围】
对于 $50\%$ 的数据,$n \le 4$,$\sum s \le 30$。
对于 $100\%$ 的数据,$1 \le T \le 15$,$1 \le n \le 100$,$0 \le \sum s \le 3141592$。
2021/5/14 加强 by [SSerxhs](https://www.luogu.com.cn/user/29826)&[滑大稽](https://www.luogu.com.cn/user/203743)