CF1747E 题解

考虑将问题抽象成：左上角为 $(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](https://codeforces.com/contest/1747/submission/179483153)