【2023 NOI 模拟赛 04】小 F 与游戏 做题记录

有一个初始为空的序列 $a$，你可以通过如下方式生成一个序列 $b$，刚开始 $b$ 为空。

接下来进行 $n$ 次操作，第 $i$ 次可选的操作如下：

• 把 $i$ 放入 $a$ 的开头；
• 把 $i$ 放入 $a$ 的末尾；

接下来再进行 $n$ 次操作，每次操作可以是下面两种中的一种：

• 把 $a$ 开头元素从 $a$ 中删除，并将其放入 $b$ 的最后；
• 把 $a$ 末尾元素从 $a$ 中删除，并将其放入 $b$ 的最后；

对于给定的 $n,k,p$，请求出所有不同的可以由以上过程生成的序列 $b$ 中有多少个满足 $b_k=1$，对 $p$（质数）取模。

$1\le k\le n\le 5\times 10^5$，$10^8\le p\le 2\times 10^9$。

注意到进行完 $1$ 和 $2$ 操作之后的序列 $a$ 一定是长这样的：

不难发现 $3$ 和 $4$ 操作一定是先取完某一边，取的时候穿插着取另一边，然后取 $1$，最后剩下的随便取。观察到以 $1$ 为中心的左边和右边的序列是本质相同的，所以可以假设取完的是左边。

不难发现，这样序列 $b$ 就会分成两部分，$1\sim k$ 是一部分，$k+1\sim n$ 是另一部分。前一部分的要求是能划分为两个单调下降的子序列，后一部分可以乱取，方案数为 $2^{n-k-1}$。设第一部分中属于左边的子序列为 $A$，属于右边的子序列为 $B$，那么两部分唯一的限制即为第二部分中属于右边的最后一个元素要小于 $B$ 的最后一个元素：

考虑计算第一部分的方案数，为了防止记重，对于一个 $b_{[1,k]}$ 的合法方案，不妨从左往右依次考虑，若 $b_i$ 可以接到 $A$ 的后面则直接接上去，否则再接到 $B$ 的后面。容易证明若 $b_{[1,k]}$ 合法则 $A$ 和 $B$ 则可以分完 $b_{[1,k]}$，那么考虑设 $dp_{i,j}$ 表示序列长度为 $i$，序列中的数两两不同，$B$ 的最后一个数是第 $j$ 小的方案数。那么考虑 $i+1$ 是在值域中哪里插入的，分为两种情况：

• 在值域的末尾（比当前最小值小）：此时一定要接在 $A$ 的最后，所以转移到 $dp_{i+1,j+1}$；
• 不在值域的末尾，但比当前第 $j$ 小数要小：此时一定要接在 $B$ 的最后，所以转移到 $dp_{i+1,2\le k\le j}$；

注意到这两种转移很像，所以可以合并为 $dp_{i,j}$ 转移到 $dp_{i+1,2\le k\le j+1}$。

考虑 $dp_{i,j}$ 可以从哪里转移到：

如图所示，所以有新的转移 $dp_{i,j}=dp_{i,j+1}+dp_{i-1,j-1}$，边界条件 $dp_{1,2}=1$（$B$ 为空默认它里面最小的是第 $i+1$ 小的），那么 $dp_{i,j}$ 相当于从 $(1,2)$ 开始，只能往下和往右上走，不越过直线 $y=x+1$，走到 $(i,j)$ 的方案数。又发现 $dp_{*,1}$ 一定是 $0$，所以可以令 $dp'_{i,j}=dp_{i,j-1}$ 即往下移，那么 $dp_{i,j}$ 就相当于是 $(1,1)$ 往下往右上走，不越过直线 $y=x$ 走到 $(i,j-1)$ 的方案数：

发现这样很丑，不好计算，那么计算 $dp'_{a,b}$ 的时候令 $pd_{i,j}=dp'_{i,a-j+1}$ 即把整体”反过来“，$dp'_{a,b}=pd_{a,a-b+1}$ 就相当于从 $(1,a)$ 往下往右走，不越过直线 $y=a-x+1$ 走到 $(a,b)$ 的方案数：

再重新对 $pd_{i,j}$ 建系，$dp'_{a,b}$ 就相当于从 $(1,1)$ 往上往右走，不越过直线 $y=x$ 走到 $(a,a-b+1)$ 的方案数：

遇到格路计数问题，先设 $\operatorname{calc}(x,y)$ 为从 $(1,1)$ 向右向上走到 $(x,y)$ 的方案数，即 $\binom{x+y-2}{x-1}$。

这是个经典问题，考虑容斥，用所有方案数减去越过直线 $y=x$ 的方案。所有方案数即为 $\operatorname{calc}(a,a-b+1)$，而越过直线的方案数可以考虑以 $y=x+1$ 为对称轴把 $(a,a-b+1)$ ”翻折“到 $(a-b,a+1)$：

这样由于第一次越过直线 $y=x$ 的位置 $(x_0,y_0)$ 一定在直线 $y=x+1$ 上，所以把 $(x_0,y_0)$ 之后的路径翻折就可以到达 $(a-b,a+1)$，而且每个不同的 $(x_0,y_0)$ 对应的路径都不一样，翻折后当然也不一样：

所以每种越过直线 $y=x$ 的路径都可以转换为从 $(1,1)$ 向上向右走到 $(a-b,a+1)$ 的路径，方案数为 $\operatorname{calc}(a-b,a+1)$，那么从 $(1,1)$ 向上向右走到 $(a,a-b+1)$ 且不越过直线 $y=x$ 的方案数即为 $\operatorname{calc}(a,a-b+1)-\operatorname{calc}(a-b,a+1)$。

这样我们就可以 $O(1)$ 计算 $dp_{i,j}$ 了，$dp_{i,j}$ 即为 $\operatorname{calc}(i,i-j+2)-\operatorname{calc}(i-j+1,i+1)$。

那么可以枚举 $j$，答案即为 $2^{n-k-1}\sum\limits_{i=2}^{k}\binom{i-1+n-k}{i-1}\left(\operatorname{calc}(k-1,k-i+1)-\operatorname{calc}(k-i,k)\right)$。

#include <iostream>
#include <cstdio>
#include <deque>
#include <set>

using namespace std;

typedef long long ll;

const int S=1000005;

int n,m;
ll p,fra[S],inv[S];

inline ll qpow(ll x,ll y)
{
	ll res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?res*x%p:res;
	return res;
}

inline ll C(int n,int m)
{
	if(n<0||m<0||n<m) return 0;
	return fra[n]*inv[n-m]%p*inv[m]%p;
}

inline void add(ll &x,ll y)
{
	x+=y;
	if(x>=p) x-=p;
}

inline ll calc(int x,int y)
{
	if(x<1||y<1) return 0;
	return C(x+y-2,x-1);
}

inline ll calcpd(int i,int j)
{
	return (calc(i,i-j+1)-calc(i-j,i+1)+p)%p;
}

int main()
{
	scanf("%d%d%lld",&n,&m,&p);
	if(m==1) return printf("%d\n",qpow(2,n-2)),0;
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=fra[i-1]*i%p;
	inv[S-3]=qpow(fra[S-3],p-2);
	for(int i=S-3;i>=1;i--) inv[i-1]=inv[i]*i%p;
	ll ans=0;
	for(int i=2;i<=m;i++)
	{
		ll prex=C(i-1+n-m,i-1)*calcpd(m-1,i-1)%p;
		add(ans,prex);
	}
	printf("%lld\n",ans*qpow(2,n-m-1)%p);
	return 0;
}