[数学记录]AT2301 [ARC068D] Solitaire
command_block
2021-05-12 15:01:27
**题意** ： 将 $1\sim n$ 按顺序全部加入双端队列（可加头可加尾），再取出（可删头可删尾）。
将取出的牌按顺序排成一个序列，称之为「删除序列」。
求有多少种删除序列，使得 $1$ 排在第 $k$ 个。答案对 $10^9+7$ 取模。
$n,k\leq 2000$ ，时限$\texttt{2s}$。
------------
> 感谢 @BILL666 题解的指导，学到许多。
先来考虑如何判定一个序列是否是「删除序列」，且满足 $1$ 排在第 $k$ 个。
观察产生删除序列的过程。
首先，双端队列填满时，一定形如单谷。从谷底 $1$ 向左右看，都是上升序列。从外往里看则是下降序列。
取出时，在取到 $1$ 之前，相当于将两个下降序列归并。于是，前 $k-1$ 个数需要满足 ： 能够划分为两个下降子序列。称这个性质是「双股的」。
在取出 $1$ 之后，我们便不再关心后面数的状况，但仍然要考虑其方案数。
此时，队列中的 $n-k$ 个数一定是有序的（谷底的一侧被拿完了）。
除了最后一个数以外，每一步从队列的两侧取都会得到不同的结果，于是方案数为 $2^{n-k-1}$。
不妨强制每次都取较大的，不难发现，这样（仍然在做归并）构造出的一定是双股序列，且这是唯一一种得到双股序列的办法。
于是，我们统计第 $k$ 个位置为 $1$ 的双股序列个数，再将答案乘以 $2^{n-k-1}$ 即可。
根据 $\rm Dilworth$ 定理，「能划分成两个下降子序列」 $\Leftrightarrow$ 「 不存在长为 $3$ 的上升子序列（三连升）」。
可以进一步发现，一个排列与其逆排列的 「双股性」 总是相同的（这不会改变偏序关系）。故「第 $k$ 个位置为 $1$ 的双股序列个数」等于「第 $1$ 个位置为 $k$ 的双股序列个数」。
考虑 $\rm DP$。记 $f[n,k]$ 表示 $n$ 元排列中第 $1$ 个位置为 $k$ 的双股序列个数。
边界 $f[1,1]=1$。
转移 ：
若 $k=n$ ，则其不可能是某个「三连升」的一部分，于是可以直接删除。
$$f[n,n]=\sum\limits_{j=1}^{n-1}f[n-1,j]$$
若 $k\neq n$ ，$k$ 是某个下降序列的开头。另一个下降序列的开头则是 $n$。
考虑排列的第二项 $p_2$ ，若 $p_2=n$ ，则可以将其直接删去。故 $f[n,k]\leftarrow f[n-1,k]$。
若 $k<p_2<n$ ，则构成三连升，不合法。
若 $p_2<k$ ，合法，故 $f[n,k]\leftarrow \sum\limits_{j=1}^{k-1}f[n-1,j]$
综上 ：
$$f[n,k]=\sum\limits_{j=1}^{\min(k,n-1)}f[n-1,j]$$
进一步推导可得 ：
$$
\begin{aligned}
f[n,1]&=f[n-1,1]\\
f[n,k]&=f[n,k-1]+f[n-1,k]\\
f[n,n]&=f[n,n-1]
\end{aligned}
$$
直接 $\rm DP$ ，复杂度为 $O(nk)$ ，可以通过。
在 [P4769 [NOI2018] 冒泡排序](https://www.luogu.com.cn/problem/P4769) 中我们得到，双股序列的个数可以写成简单的组合数。所以我们也有希望在本题中更进一步。
将式子写成主动贡献，尝试编一个组合意义 ： 路径。
$$
\begin{aligned}
f[n,k]&\rightarrow f[n+1,k]\\
f[n,k]&\rightarrow f[n,k+1]&(k<n)
\end{aligned}
$$
- 当位于 $(x,y)$ 时，可以前往 $(x+1,y)$ 或 $(x,y+1)$。但不能越过直线 $y=x$。
先不考虑「不能越过直线 $y=x$」的限制，从 $(1,1)$ 到达 $(n,k)$ 的方案数显然为 $\dbinom{n+k-2}{n-1}$。
「越过直线 $y=x$ 」等价于「达到直线 $y=x+1$」。我们将不合法方案第一次触碰 $y=x+1$ 之后的路径根据 $y=x+1$ 翻转。
于是，不合法方案与「从 $(1,1)$ 到 $(k-1,n+1)$ 的路径」一一对应。
综上我们能得到 ：
$$f[n,k]=\dbinom{n+k-2}{n-1}-\dbinom{n+k-2}{n}$$
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 4050
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN];
ll C(int n,int m)
{return fac[n]*powM(fac[m]*fac[n-m]%mod)%mod;}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
}
int n,k;
int main()
{
scanf("%d%d",&n,&k);Init(n+k);
printf("%lld",(C(n+k-2,n-1)-C(n+k-2,n)+mod)*powM(2,max(0,n-k-1))%mod);
return 0;
}
```