对于第二个人开始的每一个人,如果他比上一个人高,则站到最右边,否则站到最左边.
求对于某一个排好的序列,可以被多少种初始序列构建出,答案对任意数取模.
显然,某一个人是站在前面还是后面,只与上一个人有关.对于一个区间,考虑最后一个站进去的人,一定是最左边或者最右边的,并且这个人站在哪里,受到子区间两端的人的影响.
假设区间 中最后一个人 站在最右边,即 比 的最后一个人要高.即,区间 中,站在两边的比 矮的人都有可能是最后一个站进去的.
设 表示 内,按照 的方式确定最后一个人是否可放在最左边或最右边,的方案总数.