#P3861. Tree
Tree
题目描述
考虑一个有 个带编号顶点的有向图。每个顶点恰好有一条出边,且不存在自环。对每个顶点,记下所有直接连向它的顶点编号构成的集合。
例如,边为 、、、 的图,按顶点 的顺序得到集合 。
现在只给出这 个集合,集合所属的顶点编号已经丢失。求有多少个不同的有向图,可以得到与输入相同的集合多重集。空集可以出现多次。两种图以有向边集合是否相同来区分。若无法构成这样的图,答案为 。答案对 取模。
输入格式
有多组数据。每组第一行一个整数 (),接下来 行描述集合。每行先给出集合大小 ,再给出 个整数,表示集合中的顶点编号,范围为 到 。读到单独一行 0 时结束。
输出格式
对每组输出一行 Case #k: ans。 从 开始,ans 是取模后的答案。
样例
6
1 1
0
0
0
2 2 3
3 4 5 6
0
Case #1: 38