首页 > 其他 > 详细

[HEOI2013]SAO ——计数问题

时间:2018-05-16 11:47:58      阅读:192      评论:0      收藏:0      [点我收藏+]

题目大意:

Welcome to SAO ( Strange and Abnormal Online)。这是一个 VR MMORPG, 含有 n 个关卡。但是,挑战不同关卡的顺序是一个很大的问题。

有 n – 1 个对于挑战关卡的限制,诸如第 i 个关卡必须在第 j 个关卡前挑战, 或者完成了第 k 个关卡才能挑战第 l 个关卡。并且,如果不考虑限制的方向性, 那么在这 n – 1 个限制的情况下,任何两个关卡都存在某种程度的关联性。即, 我们不能把所有关卡分成两个非空且不相交的子集,使得这两个子集之间没有任 何限制。

对于每个数据,输出一行一个整数,为攻克关卡的顺序方案个数,mod 1,000,000,007 输出。

题目翻译:

发现最后一句话就是说:这是一棵树形图。

所以我们现在有了一棵树,只是边是有向边,挑战的限制就是边的方向,我们必须把所有指向x0的关卡全部通过,才能通过x0关卡。

其实,所有指向x0的边就是它的度数,所以可以看出来,

这个题是让我们求这个树形图有多少种拓扑序。

[HEOI2013]SAO ——计数问题

原文:https://www.cnblogs.com/Miracevin/p/9044910.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!