题解：AT_arc068_d [ARC068F] Solitaire

简单数数。

题意：很简单了，不再赘述。

做法：

首先我们考虑这个 deque 里面的数是什么样子的，发现一定是个谷型并且 \(1\) 是谷底，这个显然，那么就意味着，对于前 \(k-1\) 个位置是可以分成两个下降序列，然后 \(k\) 之后的一定是一个有序序列从前从后随便取得到的，这个部分的贡献是一定的，为 \(2^{n-k-1}\)，因为每次随便选前面和后面都可以，一定不重复。

那么我们考虑前面那个贡献，但是我们发现如果描述成两个下降序列的话非常困难，因为很容易重复计算，但是我们注意到谷型一个很好的性质：如果我们目前最小值为 \(x\)，那么下一个数可以是比 \(x\) 更小的，否则就是唯一固定的。

所以我们考虑一个 dp，\(dp_{i,j}\) 代表用了 \(i\) 个数，最小值为 \(j\)，转移有两种，一种是我下一个数填 \(<j\) 的，也就是对 \(dp_{i+1,1\cdots j-1}\) 进行转移。还有一种是我填一个大于 \(j\) 的，这个数虽然我们不知道，但是一定是另一侧的顶端是唯一的，所以也是可以转移的，但是要求 \(i\not=n-j+1\) 即还有比我大的数才行，转移到 \(dp_{i+1,j}\)。

记得最后乘上 \(2^{n-k-1}\)。