题目大意
给你一个长度为$n\le1000$的字符串S
,对于$i\in[0,k\le16]$你需要求出符合以下条件的字符串的总个数:
- 长度为$n$
- 只由
n
,o
,i
三个字符组成 - 不包含子串
noi
- 与$S$的最长公共子序列长度为$i$
一个食物网有$N$个点,代表$N$种生物,如果生物$x$可以吃生物$y$,那么从$y$向$x$连一个有向边。这个图没有环。
图中有一些点没有连出边,这些点代表的生物都是生产者,可以通过光合作用来生存; 而有连出边的点代表的都是消费者,它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了,它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为,如果它突然灭绝,那么会跟着一起灭绝的生物的种数。
举个例子:在一个草场上,生物之间的关系是:
如
如果羊都死了,那么狼会因为没有食物而灭绝,而小强可以通过吃牛、牛可以通过吃草来生存下去。所以,羊的灾难值是$1$。
但是,如果草突然灭绝,那么整个草原上的$5$种生物都无法幸免,所以,草的灾难值是$4$。
给定一个食物网,你要求出每个生物的灾难值。
Update your browser to view this website correctly. Update my browser now