将 \(1\sim n\) 顺序加入双端队列（每次可加头可加尾），再删除（每次可删头可删尾），求有多少种删除序列，使得 \(1\) 是第 \(k\) 个被删的。1
\(k\le n\le 2000\)
题解
根据套路这种计数类题我们应该考虑什么样的序列满足性质。
我们考虑我们是如何构造这段序列的。
一开始，我们将 \(1\sim n\) 的排列放入双端队列中，那应该是这样的：
然后我们考虑取出后哪些数是可以放在 \(1\) 前面的：
大概就应该是上图红色和蓝色的（当然分成两段的可能是红色而不是绿色）。
于是我们发现 \(1\) 前面的序列（包括 \(1\)）可以划分为两个单调递减的子序列（\(1\) 划给与他相邻的那个序列，反正他是最小的）：
我们发现如果是这样的话，与 \(1\) 相邻颜色序列的末尾一定是 \(1\)，另一个子序列的末尾（即最小值）一定比绿色序列中的最大值要大。
于是我们就可以愉快地 dp 辣！
显然后面那段绿色的我们是可以随便选的，即每次选左边和选右边都可以，也就是 \(2^{n-k-1}\)。
我们考虑如何 dp 出前面的序列。
一个非常 simple 的想法是令 \(f_{i,j,k}\) 表示到第 \(i\) 位，红色序列（结尾为 \(1\) 的序列，下同）的最小值为 \(j\)，蓝色序列的最小值为 \(k\)。如果我们加进去一个数字 \(x\)，我们考虑加入哪一段序列。
我们有如下贪心：我们尽量把小的数扔给红色序列（因为蓝色序列的最小值越大越可能符合条件）。如果 \(x<j\)，那我们就丢给红色序列，否则只能丢给蓝色序列。
但由于我们无法枚举 \(x\)，所以上面的 dp 行不通，但我们得到了一个有趣的贪心策略。
有上面的贪心策略，我们发现只要我们能知道所有合法的 \(x\)，我们就不必关心 \(k\) 是多少。所以我们考虑令 \(f_{i,j,k}\) 表示红色序列有 \(i\) 个数，蓝色序列有 \(j\) 个数，红色序列的最小值为 \(k\) 的方案数。
我们考虑对于一个状态 \(f_{i,j,k}\)，我们有两种方案进行转移：
- 选择一个最大的数放入蓝色序列，当然前提条件是存在这个大于 \(k\) 的数。由于这个数不可能放在红色序列里了，且如果不选最大的那个而去选其他大于 \(k\) 的数，那也就意味着这个最大的数要给绿色序列。而这样一来绿色序列就会有一个数比蓝色序列大，这显然是不合法的。也就是 \(f_{i,j,k} \to f_{i,j+1,k}\)。
- 选择一个比 \(k\) 小的数给红色序列。也就是 \(f_{i,j,k} \to f_{i+1,j,1\sim k-1}\)
这样做复杂度 \(\mathcal{O}(n^4)\)，前缀和优化一下复杂度就变成了 \(\mathcal{O}(n^3)\)
我们发现我们并不必关心 \(i\) 和 \(j\)，因为根据上面的贪心策略，我们只要知道最小的一个（红色序列的最小值显然比蓝色的最小值小，因为比红色序列最小值小的数只会被放入红色序列）就可以转移了。
我们令 \(f_{i,j}\) 表示到第 \(i\) 位，最小的一位为 \(j\)，我们发现转移方式和上面没有本质区别：
- 选择一个最大的数放入蓝色序列。\(f_{i,j}\to f_{i+1,j}\)。
- 选择一个比 \(k\) 小的数给红色序列。\(f_{i,j}\to f_{i+1,1\sim k-1}\)。
发现第一维可以直接压掉，然后直接 dp 即可。
代码
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn = 2005;
const int mod = 1000000007;
inline int pow(int a, int b)
{
if (b < 0)
return 1;
int ans = 1;
for (; b; b >>= 1, a = (LL) a * a % mod)
if (b & 1)
ans = (LL) ans * a % mod;
return ans;
}
int dp[maxn];
int main()
{
int n, k;
cin >> n >> k;
dp[n + 1] = 1;
for (int i = 1; i <= k; ++i)
{
for (int j = n; j; --j)
{
if (n - j + 1 < i)
dp[j] = 0;
else
{
dp[j] = dp[j + 1] + dp[j];
if (dp[j] >= mod)
dp[j] -= mod;
}
}
}
cout << (LL) dp[1] * pow(2, n - k - 1) % mod;
return 0;
}