格路计数

· · 算法·理论

问题 1 求 (0,0) \to (n,m) 的格路数目。

从 n+m 步中选出 n 步走 \rightarrow,答案为

\binom{n+m}{n}

问题 2 求 (0,0) \to (n,m) 的不越过 y=x+b 的格路数目。

将不合法格路碰到 y=x+b+1 后的路径关于 y=x+b+1 对称,新的终点 (n',m') 是 (n,m) 关于 y=x+b+1 的对称点。

可以证明,这是不合法格路的双射。得到答案

\binom{n+m}{n}-\binom{n+m}{m-b-1}

问题 3 求 (0,0) \to (n,m) 的不越过 y=x+b_1 和 y=x+b_2 的格路数目。

直线在同侧平凡。将越过 y=x+b_1 记作事件 \text{A},越过 y=x+b_2 记作事件 \text{B}。格路依次突破连续若干限制,得到事件序列形如 \text{ABAB}\cdots,注意连续多次越过同一条线只算一次。由容斥原理,我们要计数

\epsilon-[\text{A}]-[\text{B}]+[\text{AB}]+[\text{BA}]-[\text{ABA}]-[\text{BAB}]+[\text{ABAB}]+[\text{BABA}]

也就是在 y=x+b_1 和 y=x+b_2 间反复反射的情形。长为 i 的事件序列对应容斥系数 (-1)^i。

将终点按 \text{ABAB}\cdots 依次反射后计数,可以迭代实现,当前 (n',m') 超出第一象限时停止。复杂度 O\left(\dfrac{n+m}{L}\right)。

mint solve(int n, int m, int b1, int b2) {
    // (0, 0) -> (n, m),   b1 < 0 < b2
    int u = b1 - 1, v = b2 + 1;
    mint res = C(n+m, n);
    auto sol = [&](int st) -> void {
        int x = n, y = m;
        mint op = -1;
        while (true) {
            if (st == 0) tie(x, y) = mkpair(y-u, x+u);
            else tie(x, y) = mkpair(y-v, x+v);
            if (x < 0 || y < 0) break;
            res += op * C(x+y, x);
            st ^= 1, op = -op;
        }
    };
    sol(0), sol(1); return res;
}

问题 4 求 (0,0) \to (n,m) 的不越过 y=\frac{m}{n}x 的格路数目。

不妨设 n \perp m。我们声称有如下结论

\frac{1}{n+m} \binom{n+m}{n}

QOJ14621 Tearing Paper

定义 (0,0) \to (n,m) 的格路是合法的,当且仅当矩形 [a,c] \times [b,d] 在格路同侧。求合法格路数目。

多测,T \le 10^4,n \le 10^3,m \le 10^6,1 秒,256 MB。

:::::success[题解]

考虑分别计数不越过射线 x \le c \land y=b 和 x=a \land y \le d 的格路数目,二者相加即为所求。

以 x=a \land y \le d 的计数为例,枚举 i \le a,将格路拆成 (0,0) \to (i,d) 和 (i,d+1) \to (n,m) 两部分。

特判 (0,0) \to (a,d) \to (a+1,d) \to (n,m) 的情形。可列得答案式

\boxed{\sum_{i=0}^a \binom{i+d}{i}\binom{n-i+m-(d+1)}{n-i}}

对于 x \le c \land y=b 同理求解,单测复杂度 O(n+m) 无法通过。

注意到 n,m 不同阶,正难则反,枚举跨过 y=b 的位置 i,将不合法格路拆成 (0,0) \to (i,b) 和 (i,b+1) \to (n,m) 两部分:

根据减法原理得到

\boxed{\binom{n+m}{n} - \sum_{i=0}^{c-1} \binom{i+b}{i} \binom{n-i+m-(b+1)}{n-i}}

必有 a,c \le n,总复杂度 O(m+Tn) 可以通过。代码。

:::::

CF1942G Bessie and Cards

现有 a 张 0 卡,b 张 1 卡,c 张 2 卡和 5 张特殊卡。

抽牌开始时,从牌顶抽取前 5 张牌,可以丢弃 k 卡抽取接下来 k 张牌。若抽到全部 5 张特殊卡则获胜。

所有卡互不相同,(a+b+c+5)! 种牌堆等可能出现,求获胜概率。

多测,\sum a,\sum b,\sum c \le 2\times 10^5,2 秒,250 MB。

:::::success[题解]

抽到 1 卡以后立刻丢掉抽下一张,那么 1 卡的作用可以忽略。0 卡和特殊卡都视作 -1,2 卡视作 +1,则前缀和到达 -5 的时刻停止抽卡,获胜条件取决于这时候是否集齐特殊卡。

可以用格路计数转化条件,抽到 -1 令 y \gets y+1,抽到 +1 令 x \gets x+1,则牌堆可以刻画为 (5,0) 出发的格路,触碰 y=x 则停止游走。

枚举触碰点为坐标 k \ge 5,只要计数 (5,0) \to (k,k-1) 的不越过 y=x 的格路。将终点关于 y=x+1 对称,由单线反射容斥得

\binom{2k-6}{k-1}-\binom{2k-6}{k}

限制为前 2k 张牌必须集齐 5 张特殊卡,方案数 \binom{2k}{5}。剩余 a-(k-5) 个 -1 卡和 c-(k-5) 个 +1 卡随意排列,方案数 \binom{a+c-2k+10}{a-k+5}。

故合法方案数为

\boxed{\sum_{k=5}^n \binom{k}{5}\binom{a+c-2k+10}{c-k}\left(\binom{2k-6}{k-1}-\binom{2k-6}{k}\right)}

注意加上始终不碰到 y=x 的方案数,计算方法和上面类似,这里不赘述。

除以总数 \binom{a+c+5}{a,c,5} 得到答案。复杂度 O(n)。代码。

:::::

P4260 [Code+#3] 博弈论与概率统计

现有两个变量 a,b,初始 a=b=0。进行 n+m 轮操作,一轮操作中:

  • 令 a \gets a+1, b \gets \max(0,b-1)。概率为 p。
  • 令 a \gets \max(0,a-1), b \gets b+1。概率为 1-p。

且第一类操作恰好发生 n 次。求 a 的期望。

进行 q 次询问,每轮询问均给出 n,m,p 并输出答案。

::::::success[题解]

容易发现 p 是搞笑的,求出 \sum a 后除以 \binom{n+m}{n} 即为所求。

设第一类操作进行 x 次,第二类操作进行 y 次。忽略与 0 取 \max 的限制,则 a=x-y。

设全过程 a=0 时 -1 共进行 k 次,最终 a=n+k-m。只要算出 k 对应的方案数即可。

做一个单步容斥,即 [x=k]=[x \le k]-[x \le k-1]。根据分析,至多 k 次的充要条件为,任意时刻 y-x \le k。

将 (x,y) 拍到二维平面上,问题转化为从 (0,0) 走到 (n,m),不越过 y=x+k 的格路数目。由单线反射容斥,将终点关于 y=x+k+1 做对称可得

\binom{n+m}{n}-\binom{n+m}{m-k-1}

至少转恰好是作差,则 \text{ans}_k=\dbinom{n+m}{m-k}-\dbinom{n+m}{m-k-1}。求和即为答案。

问题转化为 q 次询问组合数下指标前缀和,莫队解决即可,复杂度 O(n\sqrt{q})。

:::::info[组合数下指标前缀和]

模板题:AT_tenka1_2014_final_d 高橋君。

进行 q 次询问,给定 n,m,求

f(n,m)=\left(\sum_{i=0}^m \binom{n}{i}\right) \bmod (10^9+7)

考察莫队思想,只要 n,m 移动后 f(n,m) 可以由原本的值 O(1) 递推得到。事实上:

前两条转移显然,后两条由组合数递推式裂项可得。

利用莫队构造,我们可以在 O(n \sqrt{q}) 的复杂度内离线解决组合数下指标前缀和的问题。

事实上这个问题也存在 O(q+m \log^2 m) 的离线解法,参见 https://www.luogu.com.cn/article/xypg20ht。

:::::

::::::

P16958 [SCCPC 2026] 括号序列

给定合法括号串 S,求有多少合法括号串 T 满足 |T| \le |S| 且 T 的字典序不大于 S。

多测,\sum |S| \le 10^6,2 秒,1024 MB。

:::::success[题解]

我们将括号串转化成格路。将左括号视作 x \gets x+1,右括号视作 y \gets y+1,则长为 2n 的合法括号串双射到 (0,0) \to (n,n) 的不跨越 y=x 的格路。

特判 T 是 S 前缀的情形后,枚举并钦定 LCP。具体地,我们枚举 S 的第 i 位,在格路上钦定这样一个结构:

在 LCP 之后 T 不受字典序限制,枚举 |T|=m,则 T 对应 (x+1,y) \to (m,m) 的格路。由单线反射容斥,将终点关于 y=x+1 作对称可得

\binom{m-(x+1)+m-y}{m-y}-\binom{m-1-(x-1)+m+1-y}{m+1-y}

转而枚举 m-y=k,整理得到 (x,y) 处的贡献为

\boxed{\sum_{k=0}^{n-y} \left(\binom{2k+y-x-1}{k}-\binom{2k+y-x-1}{k+1}\right)}

我们记

f(a,b)=\sum_{k=0}^b \binom{2k+a}{k}

则 (x,y) 处的贡献可以写作 f(y-x-1,n-y)-f(y-x-3,n-y+1)。

瓶颈在于 f 的计算,暴力可以得到 O(n^2) 做法。注意到 f 的形式是一堆组合数加和,类比组合数下指标前缀和的莫队做法,我们考虑 a,b 移动对 f 的影响。b 的移动是简单的:

\begin{aligned} f(a,b+1)&=f(a,b)+\binom{2(b+1)+2}{b+1}\\ f(a,b-1)&=f(a,b)-\binom{2b+a}{b} \end{aligned}

我们需要观察 a \gets a\pm 1 的影响。可以对 a \in [-8,-1], b\in [0,8] 进行打表:

0       0       0       0       0       0       0       0       1
0       0       0       0       0       0       0       1       10
0       0       0       0       0       0       1       9       54
0       0       0       0       0       1       8       44      209
0       0       0       0       1       7       35      155     650
0       0       0       1       6       27      111     441     1728
0       0       1       5       20      76      286     1078    4081
0       1       4       14      49      175     637     2353    8788

注意到以下等式成立:441+637=1078,1278+2353=4081,对其他位置验证也满足规律,猜测有

f(a,b)=f(a-1,b)+f(a+1,b-1)

而 f(a+1,b-1) \to f(a+1,b) 是容易的。从而

\boxed{\begin{aligned} f(a,b)&=f(a-1,b)+f(a+1,b)-\binom{2b+a+1}{b}\\ f(a-1,b)&= f(a+1,b)-f(a,b)+\binom{2b+a+1}{b} \end{aligned}}

维护 f(a,b) 和 f(a+1,b) 后可以递推 f(a-1,b),从而 a \gets a-1 解决。对 a \gets a+1 可以逆用上式同理求得。

注意到 S 的枚举过程中,只有 x \gets x+1 和 y \gets y+1 两种操作,对应的移动是 b \gets b- 1 和 a \gets a\pm 1,且指针移动总次数 O(n)。故直接维护两个 f 值的复杂度就是线性。

复杂度 O(n)。代码。

:::::

P11164 [BalkanOI 2023] Permutations

给出 1\sim n 的排列 p_i。q 次询问给出 l,r,求满足下列条件的 1\sim n 的排列数目:

  • 排列的前缀为 p_l \sim p_r。
  • 排列的 LDS 长度 \le 2。LDS 为最长下降子序列。

:::::success[题解]

先考虑没有前缀限制怎么做,打表发现答案数列的前几项是 1,1,2,5,14,42,\cdots,猜测答案为 Catalan 数 C_n。

我们尝试将合法排列和格路计数的模型建立双射。

首先考虑从排列构造格路。我们求出前缀最大值 s_i=\max \limits_{j=1}^i p_i,然后将 (i,s_i) 画在平面上,先向上再向右走即可。因为 s_i \ge i 必成立,所以这是一条始终在 y=x 上方的格路。

接着考虑从格路构造排列。先求出每个横坐标对应的高度 s_i。对于 s_i>s_{i-1} 的位置 i,必有 p_i=s_i,即 p_i 是前缀最大值。对于非前缀最大值,我们让它们按照严格递增的顺序,依次填入剩下的空位。

在这个构造中,前缀最大值和非前缀最大值构成的子序列都是递增的。由 Dilworth 定理,\text{LDS} \le 2 当且仅当排列可以被划分为至多两个递增子序列。可以看到,这确实是满足要求的。

现在我们强制排列的前缀为 a_1,a_2,\cdots,a_k,这相当于固定了格路的前半段。先假设我们会判定无解,下面按有解讨论。

记 m=\max\limits_{i=1}^k a_i,此时格路的起点变成 (k,m)。对于 <m 的非前缀最大值,它们已经被钦定了相对顺序,即按严格递增填入空位,故不会产生贡献。我们只要关注 >m 的数。用格路计数的语言来刻画,就是说从 (k,m) 出发不越过 y=x 走到 (n,n) 的格路数目。

用单线反射容斥来算,总方案数 \dbinom{2n-m-k}{n-k},将起点关于 y=x-1 作对称,不合法方案数转化成 (m+1,k-1) \to (n,n) 的朴素格路计数。问题的答案是

\boxed{\binom{2n-m-k}{n-k}-\binom{2n-m-k}{n-m-1}}

原题中 k=r-l+1,m 是区间 \max。现在的难点在于判无解,这是一个和数数没有关系的纯 ds 题。

设 [l,r] 的区间 \operatorname{mex} 为 x,将 x 加到 p_r 后面,则前缀不合法当且仅当序列 p_l,p_{l+1},\cdots,p_r,x 的 \text{LDS}>2。等价于下列两个条件至少有一个成立:

根据区间 \operatorname{mex} 等于补集 \min 的经典结论,x 可以用前后缀 \min 算出来。对上面两个条件分别讨论:

视 n,q 同阶,判定部分 O(n \log n),计数部分 O(n)。代码。

:::::