CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:arc_124 [2021/09/03 11:51]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:arc_124 [2021/09/03 19:35] (当前版本)
jxm2001
@@ 行 162: / 行 162: @@
 </hidden>
+===== F - Chance Meeting =====
+==== 题意 ====
+给定 $n\times m$ 的网格。$A$ 开始位于 $(1,1)$，可以从 $(r,c)$ 到达 $(r+1,c)$ 或 $(r,c+1)$，最终目的地为 $(n,m)$。
+$B$ 开始位于 $(n,1)$，可以从 $(r,c)$ 到达 $(r-1,c)$ 或 $(r,c+1)$，最终目的地为 $(1,m)$。
+每个时刻只有一个人能移动，问两个人恰好相遇一次的方案。两个方案不同当且仅当某一时刻移动的人物不同或人物的移动方向不同。
+==== 题解 ====
+为方便计算，令 $n\gets n-1,m\gets m-1$，坐标从 $0$ 开始计算。$B$ 选择 $(r,c)\to (r-1,c)$ 等效于 $A$ 选择 $(r,c)\to (r+1,c)$。
+于是 $A$ 最终目的地变为 $(2n,m)$，$B$ 最终目的地变为 $(n,m)$，$B$ 只在横线运动，于是可以认为两个人只能在 $(n,i)(0\le i\le m)$ 相遇。
+设两人在 $(n,i)$ 相遇，且在到达前不相遇的方案数为 $f(i)$。
+由于两人仅相遇一次，所有两人从 $(n,i)$ 出发向终点移动的过程也不相遇，该过程的逆过程可以认为是从起点出发到 $(n,m-i)$ 相遇的过程。
+由于将 $B$ 选择 $(r,c)\to (r-1,c)$ 等效于 $A$ 选择 $(r,c)\to (r+1,c)$，所以总方案数还要乘上 ${2n\choose n}$，于是合法方案数为
+$$
+\sum_{i=0}^m {2n\choose n}f(i)f(m-i)
+$$
+接下来考虑计算 $f(i)$。设 $g(i)$ 表示两个人在 $(n,i)$ 相遇的方案数，于是有 $g(i)={n+2i\choose n}{2i\choose i}$。
+$f(i)$ 等于 $g(i)$ 再减去多次相遇的方案。考虑枚举两个人在 $(n,i)$ 相遇前最后一次相遇的位置 $j$，于是两个人在 $(n,j)\to (n,i)$ 的过程中不相遇。
+可以任取一个人先走，假定先走的人的每次移动为 $+1$，后走的人的每次移动为 $-1$。
+于是问题等价于现有 $i-j$ 个 $\pm 1$，要求构造序列，使得序列中间部分前缀和大于 $0$，且序列开头是 $+1$，序列末尾是 $-1$。
+删去序列头尾，问题等价于 $i-j-1$ 个 $\pm 1$，要求构造序列，使得序列前缀和不小于 $0$。
+上述序列数对应 $C(i-j-1)$，其中 $C(n)=\frac {2n\choose n}{n+1}$ 表示卡特兰数，于是有
+$$
+f(i)=g(i)-\sum_{j=0}^{i-1}g(j)C(i-j-1)
+$$
+卷积加速即可，时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,MAXV=MAXN*3,mod=998244353;
+int quick_pow(int n,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*n%mod;
+		n=1LL*n*n%mod;
+		k>>=1;
+	}
+	return ans;
+}
+int frac[MAXV],invf[MAXV];
+int C(int n,int m){
+	return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
+}
+int Inv(int n){
+	return 1LL*invf[n]*frac[n-1]%mod;
+}
+namespace Poly{
+	const int G=3,Mod=998244353;
+	int rev[MAXN<<2],Wn[30][2];
+	void init(){
+		int m=Mod-1,lg2=0;
+		while(m%2==0)m>>=1,lg2++;
+		Wn[lg2][1]=quick_pow(G,m);
+		Wn[lg2][0]=quick_pow(Wn[lg2][1],Mod-2);
+		while(lg2){
+			m<<=1,lg2--;
+			Wn[lg2][0]=1LL*Wn[lg2+1][0]*Wn[lg2+1][0]%Mod;
+			Wn[lg2][1]=1LL*Wn[lg2+1][1]*Wn[lg2+1][1]%Mod;
+		}
+	}
+	int build(int k){
+		int n,pos=0;
+		while((1<<pos)<=k)pos++;
+		n=1<<pos;
+		_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+		return n;
+	}
+	void NTT(int *f,int n,bool type){
+		_for(i,0,n)if(i<rev[i])
+		swap(f[i],f[rev[i]]);
+		int t1,t2;
+		for(int i=1,lg2=0;i<n;i<<=1,lg2++){
+			int w=Wn[lg2+1][type];
+			for(int j=0;j<n;j+=(i<<1)){
+				int cur=1;
+				_for(k,j,j+i){
+					t1=f[k],t2=1LL*cur*f[k+i]%Mod;
+					f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+					cur=1LL*cur*w%Mod;
+				}
+			}
+		}
+		if(!type){
+			int div=quick_pow(n,Mod-2);
+			_for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
+		}
+	}
+	void mul(int *f,int _n,int *g,int _m){
+		int n=build(_n+_m-2);
+		_for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0;
+		NTT(f,n,1);NTT(g,n,1);
+		_for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod;
+		NTT(f,n,0);
+	}
+}
+void Init(){
+	int n=MAXV-1;
+	frac[0]=1;
+	_rep(i,1,n)
+	frac[i]=1LL*frac[i-1]*i%mod;
+	invf[n]=quick_pow(frac[n],mod-2);
+	for(int i=n;i;i--)
+	invf[i-1]=1LL*invf[i]*i%mod;
+	Poly::init();
+}
+int f[MAXN],g[MAXN],A[MAXN<<2],B[MAXN<<2];
+int main(){
+	Init();
+	int n=read_int()-1,m=read_int()-1,ans=0;
+	_rep(i,0,m){
+		g[i]=1LL*C(n+2*i,n)*C(2*i,i)%mod;
+		A[i]=g[i];
+		B[i]=1LL*C(2*i,i)*Inv(i+1)%mod;
+	}
+	Poly::mul(A,m,B,m);
+	f[0]=g[0];
+	_rep(i,1,m)
+	f[i]=(g[i]+1LL*(mod-2)*A[i-1])%mod;
+	_rep(i,0,m)
+	ans=(ans+1LL*f[i]*f[m-i])%mod;
+	ans=1LL*ans*C(2*n,n)%mod;
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

页面工具