赛时想出来没时间写，赛后十分钟写完过了.jpg

以下称村民为羊，玩家为人。

考虑如果所有人的方向全部相同，就可以做一个很简单的 dp：对于每个羊，考虑下一个羊是谁，并判断是否合法。

在方向不同的时候，考虑能否仍然进行这个转移。我们发现：对于一组 (i,i+1) 或者 (i,i+2) 的转移，如果两个人的方向不同，那么这组转移成立当且仅当狼的总数满足一个简单的算数关系。（比如 i 是往左，i+1 是往右，那么狼的总数就应该是 b[i]+b[i+1]。由于转移是枚举下一个羊，所以如果 i 是往左，i+2 是往右，则认为这个转移中有 i+1 是狼）

于是我们对于每个人维护一个集合，表示如果能从开头转移到这个人的话，狼的总数应该在这个集合内。感性理解：这个集合要么是全集，要么大小很小。我大胆猜测集合不是全集的时候大小不超过 2。

转移的时候，对于一组 (i,i+1) 或者 (i,i+2) 的转移，只需判断这个转移所需要的狼的总数是否在 i 的集合内即可。