# ARC068F Solitaire

Author: Fanyi Pu

Published: 2019-04-21

Canonical: <https://pufanyi.com/blog/oi-icpc/atcoder/arc068-d>

ARC068F Solitaire 题解。

将 $1\sim n$ 顺序加入双端队列（每次可加头可加尾），再删除（每次可删头可删尾），求有多少种删除序列，使得 $1$ 是第 $k$ 个被删的。<sup>[1](https://pufanyi.com/blog/oi-icpc/atcoder/arc068-d#user-content-fn-1)</sup>

$k\le n\le 2000$

## 题解

根据套路这种计数类题我们应该考虑什么样的序列满足性质。

我们考虑我们是如何构造这段序列的。

一开始，我们将 $1\sim n$ 的排列放入双端队列中，那应该是这样的：

![](https://pufanyi.com/posts/oi-icpc/atcoder/arc068-d/deque.avif)

然后我们考虑取出后哪些数是可以放在 $1$ 前面的：

![](https://pufanyi.com/posts/oi-icpc/atcoder/arc068-d/next.avif)

大概就应该是上图红色和蓝色的（当然分成两段的可能是红色而不是绿色）。

于是我们发现 $1$ 前面的序列（包括 $1$）可以划分为两个单调递减的子序列（$1$ 划给与他相邻的那个序列，反正他是最小的）：

![](https://pufanyi.com/posts/oi-icpc/atcoder/arc068-d/end.avif)

我们发现如果是这样的话，与 $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}$，我们有两种方案进行转移：

1. 选择一个最大的数放入蓝色序列，当然前提条件是存在这个大于 $k$ 的数。由于这个数不可能放在红色序列里了，且如果不选最大的那个而去选其他大于 $k$ 的数，那也就意味着这个最大的数要给绿色序列。而这样一来绿色序列就会有一个数比蓝色序列大，这显然是不合法的。也就是 $f_{i,j,k} \to f_{i,j+1,k}$。
2. 选择一个比 $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$，我们发现转移方式和上面没有本质区别：

1. 选择一个最大的数放入蓝色序列。$f_{i,j}\to f_{i+1,j}$。
2. 选择一个比 $k$ 小的数给红色序列。$f_{i,j}\to f_{i+1,1\sim k-1}$。

发现第一维可以直接压掉，然后直接 `dp` 即可。

## 代码

```cpp
#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;
}
```

## Footnotes

1. 翻译来自[luogu](https://www.luogu.org/problemnew/show/AT2301)