[Easy-Medium] AT_arc192_e [ARC192E] Snuke's Kyoto Trip

简要题意

有一个 $(W+1)\times (H+1)$ 的网格，左下角为 $(0,0)$，右上角为 $(W,H)$。网格内有一个矩形区域是不可到达的。

你需要选择一个起点，向右或向上走任意步，求方案数。答案对 $998,244,353$ 取模。

$0\leq H,W\leq 10^6$。

思路

不理解为什么有邪恶出题人喜欢出毁人心智的大型组合数学题。

Part 1

首先减少题目中的限制总是有用的，在本题中，我们可以去掉不可达区域的限制，只计算任意起点到任意终点，每次只能向右或向上走的路径数。这个问题可以分成三个部分。

最基础的部分是固定起终点的路径数，这是简单的，设起点为 $(0,0)$，终点为 $(n,m)$，则路径数为 $\binom{n+m}{n}$。

接着是固定起点的路径数。假设起点为 $(0,0)$，网格右上角为 $(n,m)$，求总路径数 $F(n,m)$，我们很容易写出式子：

$$\begin{aligned} &F(n,m)=\sum_{i=0}^{n}\sum_{j=0}^{m}\binom{i+j}{i}=\sum_{i=0}^{n}\sum_{j=0}^{i+m}\binom{j}{i}\\ &=\sum_{i=0}^{n}\binom{i+m+1}{m}\\ &=-1+\sum_{i=0}^{n+1}\binom{i+m}{m}=-1+\sum_{i=0}^{n+m+1}\binom{i}{m}\\ &=-1+\binom{n+m+2}{m+1} \end{aligned}$$

最后就是不固定起终点的路径数 $G(n,m)$，同样可以据此写出式子：

$$\begin{aligned} &G(n,m)=\sum_{i=0}^{n}\sum_{j=0}^{m}-1+\binom{i+j+2}{i+1}\\ &=-(n+1)(m+1)+\sum_{i=1}^{n+1}\sum_{j=1}^{m+1}\binom{i+j}{i}\\ &=-(n+1)(m+1)-(n+2)-(m+2)+1+\sum_{i=0}^{j=n+1}\sum_{j=0}^{m+1}\binom{i+j}{i}\\ &=-(n+2)(m+2)-1+\binom{n+m+4}{n+2} \end{aligned}$$

于是我们可以 $O(1)$ 求出 $F,G$ 两个函数的值（不计预处理阶乘及阶乘逆的时间）。

Part 2

现在我们加上矩形不可达区域的限制。发现直接计算这样的路径是极为困难的，不妨容斥，改为计算不符合限制的路径数量。于是很容易想到按照起点终点是否在不可达区域内分类：

1. 起点终点均在不可达区域内，那么就是这个矩形的不固定起终点路径数 $G(n,m)$。
2. 起点在不可达区域内，终点不在不可达区域内。那么必定经过矩形的右边界和上边界。可以尝试枚举路径上第一个边界上的格子。
   以右边界为例，则前一步一定是向右走的（如果是向上走，那么这一定不是第一个在边界上的点）。于是可以据此将路径分成两部分，一部分是到达这个格子的左边的格子的路径数（可以看成 $F(n,m)$），然后是这个格子为起点的路径数（也可以看成 $G(n,m)$）。
3. 起点不在不可达区域内。那么必定经过矩形的下边界和左边界。根据第二类的方法枚举路径上第一个边界上的格子计算即可。

时间复杂度 $O(H+W)$。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

const int N = 1e6 + 5;
int n, m, L1, R1, L2, R2, fact[N << 1], inv[N << 1];

int binom(int n, int m){ return n < m ? 0 : Mul(fact[n], Mul(inv[m], inv[n - m])); }

int F(int n, int m){ return Sub(binom(n + m + 2, n + 1), 1); }
int G(int n, int m){ return Sub(binom(n + m + 4, n + 2), Add(Mul(n + 2, m + 2), 1)); }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> L1 >> R1 >> L2 >> R2;
    fact[0] = inv[0] = fact[1] = inv[1] = 1;
    for(int i=2;i<=(n+m+4);i++){
        fact[i] = Mul(fact[i - 1], i);
        inv[i] = Mul(inv[mod % i], mod - mod / i);
    }
    for(int i=1;i<=(n+m+4);i++) inv[i] = Mul(inv[i], inv[i - 1]);
    int ans = G(n, m);
    ans = Sub(ans, G(R1 - L1, R2 - L2));
    for(int i=L1;i<=R1;i++) ans = Sub(ans, Mul(F(i, L2 - 1), F(n - i, m - L2)));
    for(int i=L2;i<=R2;i++) ans = Sub(ans, Mul(F(L1 - 1, i), F(n - L1, m - i)));
    for(int i=L1;i<=R1;i++) ans = Sub(ans, Mul(F(n - i, m - R2 - 1), F(i - L1, R2 - L2)));
    for(int i=L2;i<=R2;i++) ans = Sub(ans, Mul(F(n - R1 - 1, m - i), F(R1 - L1, i - L2)));
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan

Submission.