P1641 题解

Chaniaq_awa · 2025-10-02 23:23:57 · 个人记录

一道很好的利用转化思想的题 主要难点是如何转化题意用卡特兰数思想求解 以及建系后转化求解

首先我们会想到一个简单的dp 然后发现这个dp很像一个网格上的求解 由于有0和1的限制 所以可以很自然想到卡特兰数 这是第一次转化。

首先第一反应按纵轴为0的个数，横轴为1的个数建系，然后不可以超过对角线...这是一个很明显的方法 (我没有想出第一篇题解的优秀建系方法...)

但是我们发现了其与普通卡特兰数的求解方法不同的一点 网格大小是 n*m 的 该怎么办呢

不妨回忆普通方法 肯定有共性 所以我们考虑容斥

显然总方案数 C(n+m,n) 我们需要找到非法路径的数量 非法路径满足什么呢？ 一定是0的数量大于1的数量。表示在图上也就是路径上有节点满足 y>x 时。由于路径每次移动1单位，所以第一次违反约束的时候，路径会接触 y=x+1 非法路径一定至少一次经过经过 y = x + 1

经过一次以后 我们就可以随便选了 至于是不是反复进出 我们只需要累加这些情况即可

容易发现我们可以将y = x + 1 上一点P前面的路径对于y = x + 1 对称翻折，那么如果其想到达(n,m)必须经过y = x + 1 ,这是第二次转化 (0,0)翻折后为(-1,1)，容易发现此时非法方案数为从(-1,1)到(n,m)的方案数c(n+m,m-1) 所以答案为C(n+m,m) - C(n+m,m-1)