题意

求长度为 的序列 ，满足 ，且存在 满足 ，求序列数量。

算法（）

赛时没看这题，以为很难。。。

根据容斥原理，答案为 全部-单调不升-单调不降+不升不降。

第二个式子最后一次化简，可以看作 的方格，从左上到右下的路径条数，有 次向右， 次向下，即有重复的排列问题。