AGC040F Two Pieces

Description

有两个棋子初始点都在坐标 \(0\) ，两个棋子之间没有区别，总共要进行 \(n\) 次操作，每次操作是如下操作其中之一：

• 选择一个棋子向前移动一步。
• 选择位置较后的那个棋子，直接移动到位置较前的那个棋子的位置。

问 \(n\) 次操作后两个棋子分别在位置 A,B 的方案数，对 \(998244353\) 取模，两种方案是相同的，当且仅当两个棋子在每一步的坐标都是相同的（注意不是每一步的操作都相同）。\(A\le B\le n\le 10^7\)。

Solution

此题最难处理的无疑是对方案相同的定义：两个棋子在每一步的坐标都是相同的。对此，令最终走到 A,B 位置的棋子分别为 a,b，从始至终一直让 a 棋子在 b 的后面（否则一定与一个满足这一条件的走法等价）。

于是可以用二元组 \((x,d)\) 来表示当前的状态，\(x\) 表示 b 棋子的位置，\(d\) 表示 a 棋子与 b 棋子的状态，那么原问题等于有以下三种操作：

• \(x\) 与 \(d\) 同时加 \(1\)
• \(d--\)，但要求 \(d\ge 2\)，如果 \(d=1\) 那么这个操作与传送没有区别，因此我们不妨认为这个操作必须满足 \(d\ge 2\)。
• 令 \(d=0\)。

如果只有 \(1,2\) 两种操作，那么这等价于在二维平面上向右上走和向右走，要求除了第一步之外不能走到 \(x\) 轴及以下。设最终从 \((0,0)\) 走到 \((x,y)\)，那么根据翻折法有答案 \(=\dbinom{x+y-1}{y}-\dbinom{x+y-1}{x}\)。

而 \(3\) 操作相当于在二维平面上向下走到 \(x\) 轴上。因此可以发现 \(1\) 操作执行了恰好 \(B\) 次，然后枚举 \(2\) 操作执行的次数 \(k\)，然后考虑在操作序列中插入剩下 \(s=n-B-k\) 个 \(3\) 操作。

设进行第 \(i\) 次操作后 \(d\) 为 \(d_i\)，如果在 \(i\) 后插入一个 \(3\) 操作，就等于将图象向下移动 \(d_i\) ，也就要求不存在 \(j>i,d_j<d_i\) 。于是不妨这 \(s\) 个操作分别插入在 \(c_1,c_2,\dots c_s\) 操作之后，则相当于将图象下降了 \(\max_{i=1}^{s}d_{c_i}\)。因为我们要求最终图象下降了 \(B-k-(B-A)=A-k\) 个单位，于是必须有 \(d_{c_s}=A-k\)，并且必须是最后一个 \(d_i=A-k\) 的 \(i\)。那么此时 \(c_1,c_2,\dots c_{s-1}\) 就可以在 \(0,1,\dots,A-k\) 的最后一次出现位置中任选一个插入即可，这可以用插板法得到方案数为 \(\dbinom{s+A-k}{A-k}\)。于是问题在 \(\mathcal O(n)\) 的时间内得到了解决，注意特判 \(n-B-k=0\) 的情况。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+10,mod=998244353;
inline int ksm(int x,int y){
	int ret=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
	return ret;
}
int n,fac[N],inv[N],a,b;
inline void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
	inv[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=0;--i) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
inline int binom(int x,int y){if(x<y||y<0) return 0;return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;}
inline int dec(int x,int y){return (x-y<0)?x-y+mod:x-y;}
inline void inc(int &x,int y){x=(x+y>=mod)?x+y-mod:x+y;}
int main(){
	scanf("%d%d%d",&n,&a,&b);
	init(n<<1);
	int ans=0;
	for(int k=0;k<=a&&k<=n-b;++k){
		int x=dec(binom(b+k-1,k),binom(b+k-1,b));
		if(!b) x=1;
		if(k==a) inc(ans,x);
		else ans=(ans+1ll*x*binom(n-b-k-1+a-k,a-k))%mod;
	}
	printf("%d\n",ans);
	return 0;
}