格路计数入门

有些时候把坐标系转 45 度看着会更好理解。

Part 1 一些定义

当你在 $(x,y)$，你下一步只能走到 $(x+1,y)$ 或者 $(x,y+1)$。

若无特殊说明，所有数字均为非负整数，保证能从起点走到终点。

• $f(x1,y1,x2,y2)$ 为从 $(x1,y1)$ 走到 $(x2,y2)$ 的方案数（$x1\le x2,y1\le y2$）；
• $cf(x1,y1,x2,y2,k)$ 为从 $(x1,y1)$ 走到 $(x2,y2)$，并且和直线 $y=x+k$ 有交的方案数；
• $ncf(x1,y1,x2,y2,k)$ 为从 $(x1,y1)$ 走到 $(x2,y2)$，并且和直线 $y=x+k$ 没有交的方案数；
• $csf(n,m,k)$ 为从 $(0,0)$ 走到 $(n,m)$ 的所有方案中，和直线 $y=x+k$ 的交点个数和；
• $cbf(n,k,b)$ 为从 $(0,0)$ 走到 $(n,kn+b)$，并且和直线 $y=kx+b+1$ 有交的方案数；
• $ncbf(n,k,b)$ 为从 $(0,0)$ 走到 $(n,kn+b)$，并且和直线 $y=kx+b+1$ 没有交的方案数；
• $nc2f(n,m,k1,k2)$ 为从 $(0,0)$ 走到 $(n,m)$，并且和直线 $y=x+k1$ 与直线 $y=x+k2$ 都没有交的方案数，保证 $(0,0)$ 和 $(n,m)$ 都在两条直线之间（$k1>0$，$k2<0$）；

Part 2 正文

2.1 $f$

会有 $x2-x1$ 步向上，$y2-y1$ 步向右，它们可以任意排列，则 $f(x1,y1,x2,y2)=\binom{x2-x1+y2-y1}{x2-x1}$。

2.2 $cf$ 和 $ncf$

显然有 $ncf=f-cf$。

则只需要计算 $cf$。

分三种情况：

• 若 $x2+k<y1$ 或 $x1+k>y2$ 则直线和路径没有任何关系，则 $cf=0$；

• 若 $x2+k\le y2$ 则一定有交，那么 $cf=f$；

• 否则考虑类似将军饮马的思路，找出 $(x2,y2)$ 关于 $y=x+k$ 的对称点 $(y2-k,x2+k)$，则从 $(x1,y1)$ 到 $(y2-k,x2+k)$ 一定有交，且将第一个交点后面的路径关于 $y=x+k$ 整体翻折后与从 $(x1,y1)$ 到 $(x2,y2)$ 的和直线相交的路径构成双射：

  

  那么有 $cf(x1,y1,x2,y2,k)=f(x1,y1,y2-k,x2+k)$；

综上，有：

$cf(x1,y1,x2,y2)=\begin{cases} 0& x2+k<y1\text{ 或 }x1+k>y2\\ f(x1,y1,x2,y2)& x2+k\le y2\\ f(x1,y1,y2-k,x2+k)&x2+k>y2 \end{cases}$

$ncf$ 减一减就出来了。

2.3 $csf$

对每个 $(x,x+k)$ 算贡献，有：

$csf(n,m,k)=\sum\limits_{i=0}^n f(0,0,i,i+k)\times f(i,i+k,n,m)$

似乎没法优化，换一种思路，注意到：

• 若 $n+k\le m$ 则一定要交至少一次。那么不妨设 $csf(n,m,k)=f(0,0,n,m)+res$，其中 $res$ 为不是最后一个交点的交点个数，则有：

  $\begin{aligned} res&=\sum\limits_{i=0}^n f(0,0,i,i+k)\times(cf(i+1,i+k,n,m,k)+cf(i,i+k+1,n,m,k))\\ &=\sum\limits_{i=0}^n f(0,0,i,i+k)\times(f(i+1,i+k,n,m)+f(i,i+k+1,m-k,n+k))\\ &=\sum\limits_{i=0}^n f(0,0,i,i+k)\times f(i+1,i+k,n,m)\times 2\\ &=2\times \sum\limits_{i=0}^n f(0,0,i,i+k)\times f(i,i+k,n-1,m)\\ \end{aligned}$

  第二行到第三行是因为两个路径关于直线对称，第三行到第四行是因为先往右走一步等价于最后往左走一步。

  注意到 $\sum\limits_{i=0}^n f(0,0,i,i+k)\times f(i,i+k,n-1,m)=csf(n-1,m,k)$，那么有：

  $res=2\times csf(n-1,m,k)$

  那么不断展开下去，直到 $n=0$，得到：

  $csf(n,m,k)=\sum\limits_{i=0}^n 2^{n-i}f(0,0,i,m)=\sum\limits_{i=0}^n 2^{n-i}\binom{m+i}{m}$

• 对于 $n+k>m$ 的情况，只有 $cf(0,0,n,m,k)$ 种方案会有交。那么仍然是设 $csf(n,m,k)=cf(0,0,n,m,k)+res$，$res$ 的定义不变，那么有：

  $\begin{aligned} res&=\sum\limits_{i=0}^n f(0,0,i,i+k)\times(cf(i+1,i+k,n,m,k)+cf(i,i+k+1,n,m,k))\\ &=\sum\limits_{i=0}^n f(0,0,i,i+k)\times(f(i+1,i+k,m-k,n+k)+f(i,i+k+1,n,m))\\ &=\sum\limits_{i=0}^n f(0,0,i,i+k)\times f(i,i+k+1,n,m)\times 2\\ &=2\times \sum\limits_{i=0}^n f(0,0,i,i+k)\times f(i,i+k,n,m-1)\\ &=2\times csf(n,m-1,k) \end{aligned}$

  所以：

  $csf(n,m,k)=\sum\limits_{i=0}^m 2^{m-i}cf(0,0,n,i,k)=\sum\limits_{i=k}^m 2^{m-i}\binom{n+i}{n+k}$

那么问题转变为求解 $\sum\limits_{i=k}^n 2^{n-i}\binom{m+i}{m+k}$（$n,m,k$ 不再是原来那三个 $n,m,k$）。

遇到这种组合数求和，不妨放到杨辉三角上看看：（牢记 $\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$）

所以有：

$\sum\limits_{i=k}^n 2^{n-i}\binom{m+i}{m+k}=\sum\limits_{i=m+k+1}^{m+n+1}\binom{m+n+1}{i}$

所以：

$csf(n,m,k)=\begin{cases} \sum\limits_{i=m+1}^{m+n+1}\binom{m+n+1}{i}&n+k\le m\\ \sum\limits_{i=n+k+1}^{m+n+1}\binom{m+n+1}{i}&n+k> m \end{cases}$

2.4 $cbf$ 和 $ncbf$

只需要求 $cbf$。

设 $m=kn+b$。

枚举最后一个交点 $(p,kp+b+1)$，则交点之后的路径数为：

$f(p,kp+b+1,n,m)\\\begin{aligned}\\&=\frac{(m-kp-b-1+n-p)!}{(m-kp-b-1)!(n-p)!}\\&=\frac{(m-kp-b-1+n-p)!}{(m-kp-b)!(n-p-1)!}\times\frac{m-kp-b}{n-p}\\&=\binom{m-kp-b+n-p-1}{n-p-1}\times\frac{m-kp-b}{n-p}\\&=f(p,kp+b+1,n-1,m+1)\times\frac{kn+b-kp-b}{n-p}\\&=f(p,kp+b+1,n-1,m+1)k\\\end{aligned}$

由于所有走到 $(n-1,m+1)$ 的路径都一定会和直线相交，所以有交点的路径和最后一个交点在 $(n,kn+b+1)$ 的路径构成双射，那么有 $cbf(n,k,b)=k\binom{n+m}{n-1}=k\binom{(k+1)n+b}{n-1}$。

2.5 $nc2f$

回顾 $ncf$ 的计算方法，考虑容斥计算和两条直线有交的方案数。

注意到沿 $y=x+k1$ 翻转终点可以计算出与 $y=x+k1$ 有交的方案数，沿 $y=x+k2$ 翻转终点可以计算出与 $y=x+k2$ 有交的方案数：

但是同时和两条直线相交的路径会被算两次。

考虑终点先沿 $y=x+k1$ 翻转再沿 $y=x+k2$ 翻转后的路径，注意到每一条这样的路径先把和 $y=x+k2$ 的第一个交点后的部分翻转，再把该部分第一个和 $y=x+k1$ 的交点后的部分翻转都对应着一条和两条直线都有交的路径：

具体的，对于每一条从 $(0,0)$ 到 $(n,m)$ 的路径，设其交点序列 $b$ 为一个记录产生其每个交点的直线编号的 01 序列，例如上图红色路径的 $b$ 序列即为 $010$。

那么把终点沿 $y=x+k1$ 翻转后相当于计算有多少路径的 $b$ 序列包含了子序列 $0$，沿 $y=x+k2$ 翻转后相当于计算有多少路径的 $b$ 序列包含了子序列 $1$，先沿 $k1$ 再沿 $k2$ 翻转相当于计算有多少包含了 $10$，先 $k2$ 再 $k1$ 相当于计算有多少包含了 $01$，先 $k1$ 再 $k2$ 再 $k1$ 相当于计算有多少包含了 $010$……

接下来考虑一个很智慧的容斥，对于长 $l$ 的 $01$ 相间序列（终点翻转了 $l$ 次），其方案数对答案的贡献为 $(-1)^{l-1}$。

证明这个容斥的正确性仅需证明每种非空 $b$ 序列都会被计算恰好 $1$ 次。

对于一个非空 $b$ 序列，设其最长的 $0$ 开头的 $01$ 相间子序列长 $l_0$，$1$ 开头的长 $l_1$，显然 $|l_0-l_1|=1$。

也就是说，$l_0$ 和 $l_1$ 奇偶性不同。

注意到 $l_0$ 若为奇数则会贡献 $1$，为偶数则会贡献 $0$，$l_1$ 也一样。由于它们奇偶性不同，所以贡献和一定为 $1$，证毕。

由于 $b$ 序列最多长 $n+m$，所以时间复杂度 $O(n+m)$。

Part 3 一些技巧

3.1 连边映射

对于每一步转移都会让路径权值乘上关于 $x$ 和 $y$ 的一次代价的格路计数问题，可以考虑把每一步转移放进序列，利用分配律拆贡献，每一步转移选择前面一个和其有贡献的转移连权值为对应贡献的无向边，形成一棵树，然后对于这样的树计算权值积之和。

例如：

每一步从 $(x,y)$ 走到 $(x+1,y)$ 或 $(x,y+1)$。

• 从 $(x,y)$ 走到 $(x+1,y)$ 会让路径权值乘上 $a_1x+b_1y+w_1$；
• 从 $(x,y)$ 走到 $(x,y+1)$ 会让路径权值乘上 $a_2x+b_2y+w_2$；

求从 $(0,0)$ 走到 $(n,m)$ 的所有路径权值之和。

考虑把每一步转移放入序列 $a$ 中，$x+1$ 为 $1$，否则为 $0$，则对于每个 $a_i$：

• $a_i=0$：
  • $i$ 和它前面的每个 $1$ 都会造成 $a_1$ 的贡献，故其可以和前面的每个 $1$ 连权值为 $a_1$ 的无向边 ；
  • $i$ 和它前面的每个 $0$ 都会造成 $b_1$ 的贡献，故其可以和前面的每个 $0$ 连权值为 $b_1$ 的无向边；
  • $i$ 还会额外贡献 $w_1$ 的权值，故其可以和点 $0$ 连权值为 $w_1$ 的无向边；
• $a_i=1$ 同理，把 $a_1,b_1,w_1$ 换成 $a_2,b_2,w_2$ 即可；

由于权值乘算，故每步转移选择一条能连的无向边连，这样会形成以 $0$ 为根的一棵父亲比儿子编号小的树，对于所有这样的树算边权积的和即可。

由于 $(n,m)$ 固定，所以 $a$ 中 $0$ 和 $1$ 的个数都知道，那么用各种方法答案即可。

例题：【2024暑假集训ACM2】G.Competition

Part 4 练习

• 【2023NOI模拟赛37】商人