题目大意
有(n)条狗，其中至少有一条得了懒癌。每个人可以看到一部分狗的情况，并且每天进行一轮推断
当它推断出自己的狗一定有懒癌时，就会将自己的狗枪毙，并且所有人停止推断。如果有多个人同时推断出则同枪毙
求在所有(2^n-1)种情况中，所有有狗被杀的情况中，一共过了多少天，枪毙了多少狗。
分析
首先考虑用状压(dp)来模拟所有的情况和转移，设(dp_{S})表示集合(S)中的狗得了懒癌时的最小推断步数
我们考虑通过反推的方式进行转移，显然一个没有懒癌的狗永远不会被枪毙。
-
边界条件：当一个人能看到所有狗，并且其他狗都没有懒癌时，直接枪毙，(dp_S=1)
-
反证法：
对于一个有懒癌的狗(i)进行反证
- 先假设自己的狗没有病
- 枚举所有可能的状态，即枚举所有看不到的狗是否得了病，得到后继状态集合( ext{next}(S,i))
- 如果(k)步以内所有可能情况均已经达成了结束，在这个状态却没有，说明假设不成立，在(k+1)天就会枪毙自己的狗。
此时，设所有可能状态集合为( ext{next}(S,i))，则答案为(dp_{S,i}=max_{Tin ext{next}(S,i)}{dp_T}+1)
-
总转移：(displaystyle dp_{S}=min_{iin S} {max_{Tin ext{next}(S,i)}{dp_T}+1})
所有不会成环的状态均有结束状态（这里并没有处理枪毙了多少狗）
简化转移
从上面的转移式中容易看出：
对于(Usubseteq V)，一定有(dp_{U}leq dp_V)
故在转移时，不再需要枚举看不到的狗是否得了病，只需要考虑它们全部得病的情况。
转移出现环的性质
对于每个(i)看不到(j)的关系（(i e j)），从(i)向(j)连一条边，如果第(i)条狗有懒癌，则第(i)个点为黑点，否则为白点。
考虑简化之后的转移的过程，转移后继有着怎样的特点：
- 选择了一个(S)中的元素(i)，并且将其删除；将(i)出边的所有点加入(S)
- (S)中的元素均没有出边时，才能够保证到达边界状态
故在建成的图上，对于一个大小(>1)的强连通分量（也就是存在环的分量）
一旦其中出现了黑点，该状态就永远无法到达边界状态
同样的，如果一个点能够到达一个环，那么这个点也不能是黑点
将这些非法点剔除之后，设新的图为包含(n)个节点的( ext{DAG})
在( ext{DAG})上统计答案
上文已经提到了转移过程在( ext{DAG})上的体现，那么考虑一个状态如何到达边界：
-
选择某一个 没有其他黑点能到达 的黑点，将它删掉，加入它的出边
-
当( ext{DAG})上不存在黑点时，状态结束，1过程进行的次数就是答案
-
第一问
只需要考虑每个点被进行1操作的次数。
容易发现，如果有一个黑点能够到达(i)，(i)就会被操作一次。
故只需要统计出有多少点能够到达(i)（包括(i)自己），设为(f_i)，答案就是(sum (2^{f_i}-1)2^{n-f_i})
-
第二问
显然我们需要统计每一条狗被枪毙的次数。
考虑上面的转移对应着一个怎样的推导过程：
- 在一开始的集合枚举了一个点(i)，得到一个后继状态
- 经过一系列后继状态的转移到达边界，发现矛盾
- 一开始被枚举的那个(i)被枪毙
那么被枪毙的狗，实际上就是 某一个 没有其他黑点能到达 的黑点（也就是一开始的转移式中枚举的每一个最优的(i)）。
容易发现答案就是(sum 2^{n-f_i})