[atARC068F]Solitaire

对于最终的序列$a_{i}$，条件如下：

1.$a_{i}$是一个排列，且$a_{k}=1$

2.不存在三元组$1\le x<y<z<k$，使得$a_{x}<a_{y}<a_{z}$

3.$\forall k<x$，$a_{x}>\max_{x<y\le n}a_{y}$或$a_{x}<\max_{x<y\le n}a_{y}$

4.$\max(\min_{1\le x<y<k,a_{x}<a_{y}}a_{x},a_{k-1})>\max_{k<x\le n}a_{x}$（左式$y$的意义是要求$x$满足存在$y$，且若不存在$x$其值定义为$n+1$）

下面稍微解释一下（仅说明必要性）——

第一个条件显然，就不说明了

假设队列中的数从队首开始，依次为$b_{1},b_{2},...,b_{n}$，其中$b_{t}=1$，不难得到有$\forall 1\le i<t,b_{i}>b_{i+1}$以及$\forall i<t\le n,b_{i-1}<b_{i}$

在取出1之前，当在队首/队尾取出一个数字$x$后，考虑此时队尾/队首的数字$y$，若$x<y$则说明在$x$之前不存在比$x$小的数字，反之则说明$x$之后不存在比$x$大的数字，这等价于第2个条件

在取出1之后，队列中也就剩下一个单调的数列，此时从队首取出的数必然比之后所有数都小，从队尾取出的数必然比之后所有数都大，这等价于第3个条件

不妨假设1是从队首取出，那么考虑1取出前从队首和队尾取出的最后一个数字$x=b_{t-1}$和$y$，根据单调性$y$需要大于剩下单调队列中的最大值，也即$\max_{k<x\le n}a_{x}$

当$x>y$，不妨将队首和队尾这两段交换，因此可以看作$\max(x,y)>\max_{k<x\le n}a_{x}$

关于$\max(x,y)$的值，首先$x$和$y$中必然有一个数是$a_{k-1}$，不妨假设为$x$，之后从$a_{k-1}$向前，找到第一个不单调递增的位置，将这个作为$y$一定最大，根据条件2，其之前所有数都比其小，因此$y=\min_{1\le x<y<k,a_{x}<a_{y}}a_{x}$，而$\max(x,y)>\max_{k<x\le n}a_{x}$即等价于第4个条件

当我们确定$a_{i}$的前$k$个数后，根据条件1，令未出现的数构成集合$S$，那么剩下的数即$S$中所有数的一个排列，因此有$\max_{k<x\le n}a_{x}=\max_{x\in S}x$，由此即可判定条件4，另外条件1和2也可以容易地判定

此时，对于条件3，除去$a_{n}$以外，每一个数不可能同时满足这两个条件，当确定每一个数满足的条件后，不难发现我们可以恰好构造出一组解（若满足$a_{x}>\max_{x<y\le n}a_{x}$，则$a_{x}$为$S$的最大值，之后删除$S$中的最大值，另一种类似），因此解数即为$2^{n-k-1}$

对于前$k-1$个数（$a_{k}=1$即不需要考虑），考虑dp计算，用$f_{i,j,k}$表示确定前$i$个数、$\min_{1\le x\le i}a_{x}=j$且$\max(\min_{1\le x<y\le i,a_{x}<a_{y}}a_{x},a_{i})=k$的方案数

由于排列的性质，我们要考虑已经出现过的数，根据$j$最小显然先比$j$小的数必然都没有出现，其次比$k$大的数字必然都出现过，原因如下：

若$k=n+1$显然成立，因此$k\ne n+1$，即存在这样的$(x,y)$满足$a_{x}<a_{y}$，根据条件2之后就不能出现比$k$大的数（直至1出现为止），同时$k$单调不增，而最终这个未出现的数在$S$中，有$\max_{x\in S}x>k$，不满足条件4

下面考虑转移，分两类讨论：

1.当我们新加入一个比$j$小的数字，显然$j$转换为新的数，$k$不变

2.当我们新加入一个比$k$小且比$j$大的数字$x$，由于$j$和$x$满足，因此$k=\max(j,x)=x$，而比$k$大的数都需要出现，因此$x$必然是比$k$小且最大的未出现的数

当然，$x$需要比$j$大，即$j$到$k$之间的数不能全部出现，显然这等价于$n-j+1>i$

事实上，我们发现$k$这个状态是多余的，用$f_{i,j}$表示前$i$个数且$\min_{1\le x\le i}a_{x}=j$，综上即可递推计算，$f_{i,j}$转移到$f_{i+1,k}$（$2\le k<j$），若$n-j+1>i$，还可以转移到$f_{i+1,j}$

将这个过程转换为$f_{i,j}=\sum_{k=j}^{n+1}f_{i-1,k}$（特别的，若$n-j+1<i$则$f_{i,j}=0$），后缀和优化即可，时间复杂度为$o(n^{2})$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2005

 4 #define mod 1000000007

 5 int n,k,ans,f[N][N],sum[N][N];

 6 int main(){

 7     scanf("%d%d",&n,&k);

 8     f[0][n+1]=1;

 9     for(int i=2;i<=n+1;i++)sum[0][i]=1;

10     for(int i=1;i<k;i++){

11         for(int j=2;j<=n+1;j++)

12             if (n-j+1<i)f[i][j]=0;

13             else f[i][j]=sum[i-1][j];

14         sum[i][n+1]=f[i][n+1];

15         for(int j=n;j>1;j--)sum[i][j]=(sum[i][j+1]+f[i][j])%mod;

16     }

17     ans=sum[k-1][2];

18     for(int i=1;i<n-k;i++)ans=2*ans%mod;

19     printf("%d",ans);

20 }

巴特西

[atARC068F]Solitaire

最新文章

热门文章