AGC040F Two Pieces

Description

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

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

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

Solution

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

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

(x) 与 (d) 同时加 (1)
(d--)，但要求 (dge 2)，如果 (d=1) 那么这个操作与传送没有区别，因此我们不妨认为这个操作必须满足 (dge 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
",ans);
	return 0;
}