AT2301题解

· · 题解

这是一个线性的做法

称一个序列是 hh 的当且仅当它可以被拆分为两个单调递减的子序列。

不难发现，一个双端队列可以由操作得到当且仅当它从开头到 1 递减从 1 到结尾递增。

当这个排列的前 m 项确定了后，双端队列中剩下的数一定是单调的。

因此我们可以先统计合法的序列中后n-m 个单调递减的序列个数，然后最后再将答案乘上 2^{n-m-1} 即可（第 m+1\sim n-1 次都可以从左侧或右侧取出）。

根据大小关系，这等价于求第 m 项为 1 的 hh 的序列的个数。

对于一个排列，由 Dilworth 定理，它是 hh 的当且仅当其中不存在顺次递增的三项。因此一个排列和它的逆的 hh 性是相同的（可以考虑函数与其反函数的关系）。问题转化为求 p_1=m 的 hh 的排列的个数。

考虑 dp ,不妨记 f_{n,i} 表示长度为 n 的且第一项为 i 的 hh 的排列个数。

考虑转移

若 i=n ,则其不可能出现在顺次递增的三项中，直接删去，因此f_{n,i}=\sum_{1\le j<i}f_{n-1,j}。

若 i<n ,则考虑 p_2

综上

f_{n,i}=\sum_{1\le j<i}f_{n-1,j}(i=n) f_{n,i}=\sum_{1\le j\le i}f_{n-i,j}(i<n)

最终答案就是 f_{n,m}。

再推演下,当n>1时有

f_{n,1}=f_{n-1,1} f_{n,i}=\sum_{1\le j\le i-1}f_{n-1,j}+f_{n-1,i}=f_{n,i-1}+f_{n-1,i} f_{n,n}=\sum_{1\le j\le n-1}f_{n-1,j}=f_{n,n-1}

发现这是经典的走格子 dp ,即 f_{n,m} 代表从 (2,1) (为什么不是 (1,1)? 上面的递推式只在 n>1 的情况下才成立) 每次向上或向右走到 (n,m) 且不超过 y=x 这条线的方案数。

类似卡特兰数的推导，首先总路径显然为 \binom{n+m-3}{n-2}。

超过 y=x 等价于不经过 y=x+1 这条线。

对于一种不合法的行走方案，将其第一次和 y=x+1 相交后的路径沿y=x+1 进行翻折，这对应着唯一一条从 (2,1) 出发到 (m-1,n+1) 的路径，因此不合法方案数为 \binom{n+m-3}n。

综上

f_{1,1}=1 f_{n,m}=\binom{n+m-3}{n-2}-\binom{n+m-3}n(n>1)

答案为 2^{n-m-1}\times f_{n,m}。

复杂度

\mathcal O(n+q)

code

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=3e6+5;
int pw[N<<1],fac[N<<1],fiv[N<<1];
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int qpow(int x,int y)
{
    int ans=1;
    for(;y;y>>=1,x=1ll*x*x%mod)
        if(y&1)ans=1ll*ans*x%mod;
    return ans;
}
inline void pre(int n)
{
    pw[0]=1;for(int i=1;i<=n;++i)pw[i]=add(pw[i-1],pw[i-1]);
    fac[0]=1;for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
    fiv[n]=qpow(fac[n],mod-2);
    for(int i=n-1;~i;--i)fiv[i]=1ll*fiv[i+1]*(i+1)%mod;
}
inline int binom(int x,int y)
{
    if(y==0)return 1;
    if(x<0||y<0||x<y)return 0;
    return 1ll*fac[x]*fiv[y]%mod*fiv[x-y]%mod;
}
int n,m;
int main()
{
    pre(4e3);
    scanf("%d%d",&n,&m);
    if(n==1&&m==1){puts("1");return 0;}
    printf("%d\n",1ll*pw[max(0,n-m-1)]*dec(binom(n+m-3,n-2),binom(n+m-3,n))%mod);
    return 0;
}