专栏文章

题解：AT_arc192_e [ARC192E] Snuke's Kyoto Trip

eemmoy
AT_arc192_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq909xq
此快照首次捕获于
2025/12/04 00:55
3 个月前
此快照最后确认于
2025/12/04 00:55
3 个月前
查看原文

题目大意

给你一个大矩形，左下角为 (0,0)(0,0)，右上角为 (W,H)(W,H)，中间挖掉一个小矩形，左下角为 (L,D)(L,D)，右上角为 (R,U)(R,U)。
规定路径是从起点开始只能向上或向右走到终点停止的运动轨迹。
求大矩形中有多少条路径不经过小矩形。

解法

一步一步推。
考虑弱化版：给定起点 (x1,y1)(x_1,y_1) 与终点 (x2,y2)(x_2,y_2)，求有多少条不同的路径。
我们发现，要从起点走到终点，一共要走 (x2−x1)+(y2−y1)(x_2-x_1)+(y_2-y_1) 步，其中要向右走 x2−x1x_2-x_1 步。
所以就相当于在 (x2−x1)+(y2−y1)(x_2-x_1)+(y_2-y_1) 步里选 x2−x1x_2-x_1 步向右走，于是就有 ((x2−x1)+(y2−y1)x2−x1)\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1} 种路径。
我们发现，我们并不在意起点与终点究竟是哪两个点，我们只在意他们的横坐标差与纵坐标差。
所以我们可以知道，当起点与终点横坐标差为 xx，纵坐标差为 yy 时，不同的路径条数共有 (x+yx)\binom{x+y}{x}。
现在我们设 f(x,y)f(x,y) 表示当起点与终点横坐标差为 xx，纵坐标差为 yy 时，不同的路径条数共有多少条，即 f(x,y)=(x+yx)f(x,y)=\binom{x+y}{x}。
由此可以得出一个性质：f(x,y)=f(y,x)f(x,y)=f(y,x)。
我们观察一下起点到终点的路径。
设起点与终点横坐标差为 xx，纵坐标差为 yy。
每条路径肯定会在与起点横坐标相差 x−1x-1 的那一列往右走一列，再向上走（可能不用）到达终点，而向右拐的点的坐标一共有 yy 种，于是可以得到一个式子：
f(x,y)=∑y′=0yf(x−1,y′)f(x,y)=\sum_{y'=0}^yf(x-1,y')
考虑另一个弱化问题：在一个 N×MN\times M 矩形中，若固定起点为左下角或终点为右上角，一共有多少条不同的路径。
由于固定终点和固定起点可以互相转化，所以只考虑固定终点的情况。
于是我们可以枚举所有可能的 xx 与 yy。
所以易得式子：
∑x=0N∑y=0Mf(x,y)\sum_{x=0}^N\sum_{y=0}^Mf(x,y)
考虑化简这个式子。
根据之前的 f(x,y)=∑y′=0yf(x−1,y′)f(x,y)=\sum_{y'=0}^yf(x-1,y')，原式可化为
∑x=0Nf(x+1,M)=∑x=1N+1f(x,M)=∑x=0N+1f(M,x)−f(0,M)=f(M+1,N+1)−1\begin{aligned} &\sum_{x=0}^Nf(x+1,M)\\ =&\sum_{x=1}^{N+1}f(x,M)\\ =&\sum_{x=0}^{N+1}f(M,x)-f(0,M)\\ =&f(M+1,N+1)-1 \end{aligned}
于是我们记 sqr(N,M)=∑x=0N∑y=0Mf(x,y)=f(M+1,N+1)−1sqr(N,M)=\sum_{x=0}^N\sum_{y=0}^Mf(x,y)=f(M+1,N+1)-1。
再考虑一个弱化问题：在 N×MN\times M 的矩阵中，一共有多少条不同的路径。
于是我们可以枚举终点
容易列出式子：
∑N′=0N∑M′=0Msqr(N′,M′)\sum_{N'=0}^N\sum_{M'=0}^Msqr(N',M')
继续化简。
∑N′=0N∑M′=0Msqr(N′,M′)=∑N′=0N∑M′=0M(f(N′+1,M′+1)−1)=∑N′=0N∑M′=0Mf(N′+1,M′+1)−∑N′=0N∑M′=0M1=∑N′=1N+1∑M′=1M+1f(N′,M′)−(N+1)(M+1)=∑N′=0N+1∑M′=0M+1f(N′,M′)−∑N′=1N+1f(N′,0)−∑M′=1M+1f(M′,0)−f(0,0)−(N+1)(M+1)=sqr(N+1,M+1)−(N+1)−(M+1)−1−(N+1)(M+1)=(f(N+2,M+2)−1)−(N+2)(M+2)=f(N+2,M+2)−(N+2)(M+2)−1\begin{aligned} &\sum_{N'=0}^N\sum_{M'=0}^Msqr(N',M')\\ =&\sum_{N'=0}^N\sum_{M'=0}^M(f(N'+1,M'+1)-1)\\ =&\sum_{N'=0}^N\sum_{M'=0}^Mf(N'+1,M'+1)-\sum_{N'=0}^N\sum_{M'=0}^M1\\ =&\sum_{N'=1}^{N+1}\sum_{M'=1}^{M+1}f(N',M')-(N+1)(M+1)\\ =&\sum_{N'=0}^{N+1}\sum_{M'=0}^{M+1}f(N',M')-\sum_{N'=1}^{N+1}f(N',0)-\sum_{M'=1}^{M+1}f(M',0)-f(0,0)-(N+1)(M+1)\\ =&sqr(N+1,M+1)-(N+1)-(M+1)-1-(N+1)(M+1)\\ =&(f(N+2,M+2)-1)-(N+2)(M+2)\\ =&f(N+2,M+2)-(N+2)(M+2)-1\\ \end{aligned}
记 all(N,M)=∑N′=0N∑M′=0Msqr(N′,M′)=f(N+2,M+2)−(N+2)(M+2)−1all(N,M)=\sum_{N'=0}^N\sum_{M'=0}^Msqr(N',M')=f(N+2,M+2)-(N+2)(M+2)-1。
回到原问题。
我们可以考虑容斥，即总路径条数减去不合法的路径条数。
总路径条数很简单，即 all(W,H)all(W,H)。
不合法的路径分为三种。
  • 起点与终点都在小矩形里的路径。
  • 起点在小矩形外，途中经过小矩形的路径（终点在或不在小矩形里都算）。
  • 起点在小矩形内，终点在小矩形外的路径。
先看第一种，很简单，答案就是 all(r−l,u−d)all(r-l,u-d)。
对于第二种，路径会从小矩形下面或左面切入矩形，所以，原路径相当于两条路径拼起来。
设路径在小矩形中第一个点是 (x2,y2)(x_2,y_2) ，是从 (x1,y1)(x_1,y_1) 这个点进入的（从下面进入矩形左下角与从左面进入矩形左下角是不一样的）。
容易得出答案为 sqr(x1,y1)×sqr(W−x2,H−y2)sqr(x_1,y_1)\times sqr(W-x_2,H-y_2)。
由于只需枚举小矩形下面与左面的点，所以时间复杂度是 O(H+W)\mathcal{O}(H+W) 的。
对于第三种，路径会从小矩形上面或右面切出矩形。
同理，设路径在小矩形中最后一个点是 (x1,y1)(x_1,y_1) ，接下来会走到 (x2,y2)(x_2,y_2) 这个点（从矩形右上角往上走与从矩形右上角往右走是不一样的）。
容易得出答案为 sqr(x1−L,y1−D)×sqr(W−x2,H−y2)sqr(x_1-L,y_1-D)\times sqr(W-x_2,H-y_2)。
由于只需枚举小矩形上面与右面的点，所以时间复杂度还是 O(H+W)\mathcal{O}(H+W) 的。
总时间复杂度是 O(H+W)\mathcal{O}(H+W) 的。

code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6;
const int p=998244353;
int n,m,ans;
int l,r,d,u;
int fac[N+10],inv[N+10];
int ksm(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=a*a%p) if(b&1) ans=ans*a%p;
	return ans;
}
int C(int n,int m){
	return fac[m]*inv[n]%p*inv[m-n]%p;
}
int f(int n,int m){
	return C(n,n+m);
}
int all(int n,int m){
	return (f(n+2,m+2)-(n+2)*(m+2)%p-1+2*p)%p;
}
int sqr(int n,int m){
	return (f(n+1,m+1)-1+p)%p;
}
signed main(){
	cin>>n>>m>>l>>r>>d>>u;
	fac[0]=1;
	for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%p;
	inv[N]=ksm(fac[N],p-2);
	for(int i=N;i>=1;i--) inv[i-1]=inv[i]*i%p;
	ans=(all(n,m)-all(r-l,u-d)+p)%p;//总路径数减第一类不合法路径数
	int sum=0;
    //第二类不合法路径数
	for(int i=l;i<=r;i++){
		sum=(sum+sqr(n-i,m-d)*sqr(i,d-1)%p)%p;
	}
	for(int i=d;i<=u;i++){
		sum=(sum+sqr(m-i,n-l)*sqr(i,l-1)%p)%p;
	}
    //第三类不合法路径数
	for(int i=l;i<=r;i++){
		sum=(sum+sqr(n-i,m-u-1)*sqr(i-l,u-d)%p)%p;
	}
	for(int i=d;i<=u;i++){
		sum=(sum+sqr(m-i,n-r-1)*sqr(i-d,r-l)%p)%p;
	}
	cout<<(ans-sum+p)%p;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...