[数学记录]AT2301 [ARC068D] Solitaire
command_block
·
·
个人记录
题意 ： 将 1\sim n 按顺序全部加入双端队列（可加头可加尾），再取出（可删头可删尾）。
将取出的牌按顺序排成一个序列，称之为「删除序列」。
求有多少种删除序列，使得 1 排在第 k 个。答案对 10^9+7 取模。
------------
> 感谢 @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] 冒泡排序 中我们得到，双股序列的个数可以写成简单的组合数。所以我们也有希望在本题中更进一步。
将式子写成主动贡献，尝试编一个组合意义 ： 路径。
\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)。
#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;
}