#P3861. Tree

    ID: 3064 传统题 3000ms 64MiB 尝试: 39 已通过: 22 难度: 6 上传者: 标签>CF2100提高容斥原理计数 DP普通多项式乘法倒序更新避免重复使用排列数计算By

Tree

题目描述

考虑一个有 nn 个带编号顶点的有向图。每个顶点恰好有一条出边,且不存在自环。对每个顶点,记下所有直接连向它的顶点编号构成的集合。

例如,边为 1→21\to2、2→42\to4、3→13\to1、4→14\to1 的图,按顶点 1,2,3,41,2,3,4 的顺序得到集合 {3,4},{1},∅,{2}\{3,4\},\{1\},\varnothing,\{2\}。

现在只给出这 nn 个集合,集合所属的顶点编号已经丢失。求有多少个不同的有向图,可以得到与输入相同的集合多重集。空集可以出现多次。两种图以有向边集合是否相同来区分。若无法构成这样的图,答案为 00。答案对 109+710^9+7 取模。

输入格式

有多组数据。每组第一行一个整数 nn(1≤n≤10001\le n\le1000),接下来 nn 行描述集合。每行先给出集合大小 pp,再给出 pp 个整数,表示集合中的顶点编号,范围为 11 到 nn。读到单独一行 0 时结束。

输出格式

对每组输出一行 Case #k: ans。kk 从 11 开始,ans 是取模后的答案。

样例

6
1 1
0
0
0
2 2 3
3 4 5 6
0
Case #1: 38

原 BZOJ 题面存档