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

emmoy · 2025-02-15 15:42:42 · 题解

题目大意

给你一个大矩形，左下角为 (0,0)，右上角为 (W,H)，中间挖掉一个小矩形，左下角为 (L,D)，右上角为 (R,U)。

规定路径是从起点开始只能向上或向右走到终点停止的运动轨迹。

求大矩形中有多少条路径不经过小矩形。

解法

一步一步推。

考虑弱化版：给定起点 (x_1,y_1) 与终点 (x_2,y_2)，求有多少条不同的路径。

我们发现，要从起点走到终点，一共要走 (x_2-x_1)+(y_2-y_1) 步，其中要向右走 x_2-x_1 步。

所以就相当于在 (x_2-x_1)+(y_2-y_1) 步里选 x_2-x_1 步向右走，于是就有 \binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1} 种路径。

我们发现，我们并不在意起点与终点究竟是哪两个点，我们只在意他们的横坐标差与纵坐标差。

所以我们可以知道，当起点与终点横坐标差为 x，纵坐标差为 y 时，不同的路径条数共有 \binom{x+y}{x}。

现在我们设 f(x,y) 表示当起点与终点横坐标差为 x，纵坐标差为 y 时，不同的路径条数共有多少条，即 f(x,y)=\binom{x+y}{x}。

由此可以得出一个性质：f(x,y)=f(y,x)。

我们观察一下起点到终点的路径。

设起点与终点横坐标差为 x，纵坐标差为 y。

每条路径肯定会在与起点横坐标相差 x-1 的那一列往右走一列，再向上走（可能不用）到达终点，而向右拐的点的坐标一共有 y 种，于是可以得到一个式子：

考虑另一个弱化问题：在一个 N\times M 矩形中，若固定起点为左下角或终点为右上角，一共有多少条不同的路径。

由于固定终点和固定起点可以互相转化，所以只考虑固定终点的情况。

于是我们可以枚举所有可能的 x 与 y。

所以易得式子：

考虑化简这个式子。

根据之前的 f(x,y)=\sum_{y'=0}^yf(x-1,y')，原式可化为

于是我们记 sqr(N,M)=\sum_{x=0}^N\sum_{y=0}^Mf(x,y)=f(M+1,N+1)-1。

再考虑一个弱化问题：在 N\times M 的矩阵中，一共有多少条不同的路径。

于是我们可以枚举终点

容易列出式子：

继续化简。

记 all(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(r-l,u-d)。

对于第二种，路径会从小矩形下面或左面切入矩形，所以，原路径相当于两条路径拼起来。

设路径在小矩形中第一个点是 (x_2,y_2) ，是从 (x_1,y_1) 这个点进入的（从下面进入矩形左下角与从左面进入矩形左下角是不一样的）。

容易得出答案为 sqr(x_1,y_1)\times sqr(W-x_2,H-y_2)。

由于只需枚举小矩形下面与左面的点，所以时间复杂度是 \mathcal{O}(H+W) 的。

对于第三种，路径会从小矩形上面或右面切出矩形。

同理，设路径在小矩形中最后一个点是 (x_1,y_1) ，接下来会走到 (x_2,y_2) 这个点（从矩形右上角往上走与从矩形右上角往右走是不一样的）。

容易得出答案为 sqr(x_1-L,y_1-D)\times sqr(W-x_2,H-y_2)。

由于只需枚举小矩形上面与右面的点，所以时间复杂度还是 \mathcal{O}(H+W) 的。

总时间复杂度是 \mathcal{O}(H+W) 的。

code

#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;
}