CF1747E 题解

EuphoricStar · 2022-11-06 13:01:04 · 题解

考虑将问题抽象成：左上角为 (0,0)、右下角为 (n,m) 的网格图，求所有满足至少有一条 只向下或向右走的路径 经过点集内所有点的的不同的点集大小之和。

显然对于一个合法的点集，经过它的路径可能不止一条，去重也很麻烦。考虑钦定两个点间的访问顺序，比如先向下再向右走，这样对于每个合法的点集，都有且仅有一条经过它的路径。

将路径的 拐点 分为两类：先向右再向下和先向下再向右。如下图，红色点表示第一类拐点，蓝色点表示第二类拐点。

考虑 枚举先向右再向下的拐点个数 ，设有 i 个。选择拐点的方案为 \dbinom{n}{i}\dbinom{m}{i}（纵坐标范围 [0,n-1]，横坐标范围 [1,m]）。这样就唯一确定了一条路径。路径上还有 s=n+m-i-1 个点，这 i 个点可以任选，总贡献为 \sum\limits_{j=0}^s \dbinom{s}{j}(i+2+j) = (i+2)2^s + \sum\limits_{j=0}^s \dbinom{s}{j}j。

考虑 \sum\limits_{j=0}^s \dbinom{s}{j}j 这部分如何快速计算。注意到 \sum\limits_{j=0}^s \dbinom{s}{j}j = \sum\limits_{j=0}^s \dbinom{s}{j}(s-j)，相加再除以 2 后得原式 = s2^{s-1}。

code