当前位置: 首页 > news >正文

卡特兰数与反射容斥

不知所云。


卡特兰数

卡特兰数是一种 OI 中可能常用的序列,序列前几项为:\(1, 2,5,14,42,132,429,1430,4862\),我们记作 \(H_i\)

卡特兰数有以下应用:

  • 求长度为 \(n\) 的合法出栈序列。
  • 求长度为 \(2n\) 的合法括号序列。
  • 求从 \((0,0)\)\((n,n)\),其中不跨过 \(y = x\) 这条直线的方案数。
  • ……

仔细思考后就会发现上述三种问题本质上都是同一类,都可以抽象成第三个问题来解决。

我们先研究最后一个问题,我们先写出来一个递推形式的计算方法。

我们枚举第一个与 \(y = x\) 交上的点,就有:

\[H_n = \sum_{i = 1}^{n} H_{i - 1} H_{n - i} = \sum_{i = 0}^{n - 1} H_i H_{n - i - 1} \]

证明可以考虑从 \((0,0)\) 走到 \((i, i)\) 且不经过 \(x = y\) 的方案数为 \(H_{i - 1}\),从 \((i, i)\) 走到 \((n, n)\) 且不跨过 \(y = x\) 的方案数为 \(H_{n - i}\),注意此处用词不同。

接下来我们考虑如何写出来一个 \(O(1)\) 的式子,接下来就是玄学:

我们将第一次到达 \(y = x + 1\) 的路径上的点之后的路径沿 \(y = x + 1\) 对称过去,这样就会到达 \((n - 1, n + 1)\) 可以证明能够到达 \((n - 1, n + 1)\) 的路径与非法到达 \((n, n)\) 的路径一一对应,然后我们就得到了:

\[H_n = C_{2n}^{n} - C_{2n}^{n - 1} \]

反射容斥

网格上只有一条线不能经过的已经解决了,接下来我们解决有两条线不能经过的,我们记录这两条直线为 \(A, B\)。那么我们可以把与一条线一直相交的方案只记录第一次。我们把 \(f(ABA)\) 记作先与 \(A\) 相交,接着与 \(B\) 相交,最后与 \(A\) 再相交一次后到达 \((n, n)\) 的方案数。

那么根据容斥原理,答案就为:

\[f(\phi) - f(A) - f(B) + f(AB) + f(BA) - f(ABA) - f(BAB) + ... \]

接下来我们考虑如何计算 \(f\) 函数。

首先 \(f(A)\) 是将 \((n, n)\) 关于 \(A\) 对称后任走到达那个点的方案数,\(f(B)\) 是将 \((n, n)\) 关于 \(B\) 对称后任走到达那个点的方案数,这两个在上面就已经讨论过了。

之后我们考虑先解决 \(f(AB)\) 之后直接就能类比出 \(f\) 函数如何解决。

我们将 \((n,n)\) 关于 \(B\) 对称,这样可以求出来 \(f(B)\),然后把这个对称后的点在关于 \(A\) 对称,这样可以就可以任走求出 \(f(AB)\)

之后我们就解决了这个问题,来看一下题。

「JLOI2015」骗我呢

这个大力 \(O(nm)\) dp 是好做的,我们考虑设以下状态:\(dp_{i,j}\) 表示前 \(i\) 行,\(j\) 没出现的方案数,就有:

\[dp_{i, j} = \sum_{k = 0}^{j + 1} dp_{i - 1, k} \]

我们画个转移的图:

image

你就会发现这样还是太复杂了,考虑如何简化:

image

但是这个斜线看着让人难受,于是我们给他拉直:

image

注意:此处的灰色点是我们建出的虚点,仅仅是辅助转移用,之后我们给他套到坐标系里:

image

你就发现问题就变为了到达 \((n + m + 1, n)\) 且不经过 \(y = x + 1\)\(y = x - (m + 2)\) 的方案数,反射容斥以下就做完了。

http://www.hskmm.com/?act=detail&tid=19068

相关文章:

  • 题解:QOJ9619/洛谷13568 [CCPC 2024 重庆站] 乘积,欧拉函数,求和(数论+状压DP)
  • Momentum Gradient Descent(动量梯度下降)
  • README
  • Halcon算子——2D几何变换
  • 深入解析:深度解析 CUDA-QX 0.4 加速 QEC 与求解器库
  • 实验作业1
  • 《C++程序设计》笔记p4 - 指南
  • 电脑显示器黑屏(闪烁:隔几秒中黑一两秒),向日葵远程正常——DeepSeek问答
  • 实用指南:iOS 26 兼容测试实战,机型兼容、SwiftUI 兼容性改动
  • 大中午记梦
  • 概率/期望 $dp$
  • 9.21~9.27 周总结
  • Jetbrains 全家桶激活码激活
  • 【深度学习计算机视觉】07:单发多框检测(SSD) - 指南
  • MZOI 2025.9.27
  • 原码 反码 补码
  • Spring Framework 远程命令执行漏洞
  • 配置本地环境以管理Git多账户SSH连接
  • Pod、 PVC 、PV的
  • 百度网盘ByPy使用配置指南
  • 完整教程:AI 术语通俗词典:Diffusion Models(扩散模型)
  • pip安装依赖包报错内容为User defined options,Native files 如何解决
  • edu 107 E(概率期望, dp)
  • 2025 年空气离合器生产厂家推荐榜:电网冲击缓解技术与可靠性测评,单片空气离合器,多片空气离合器,空气离合器摩擦片,空气离合器密封件公司推荐
  • Spring MVC的双向数据绑定
  • 抽象化编程(Abstraction in Programming)
  • 9月27日
  • 配置RedisTemplate序列化机制
  • 优化器(Optimizer)
  • 2025 年气动离合器品牌推荐排行榜发布,聚焦博得 PLC 控制技术与降本优势,常开式气动离合器,多片式气动离合器,气动离合器电磁阀,气动离合器气缸,单片式气动离合器工厂推荐