[CF559C] Gerald and Giant Chess(动态规划)

题目链接

题解

先介绍一个东西:多重集(multiset)的全排列(这里是特殊情况,即选的元素个数不超过任意集合中元素个数的情况)
我们定义集合的集合为多重集,比如我有 $a_1$ 个 $1$ , $a_2$ 个 $2$ …… $a_n$ 个 $n$ 。
那么写成多重集就是 \(\left\{\left\{a_1·1\right\},\left\{a_2·2\right\},\cdots,\left\{a_n·n\right\}\right\}\)
如果我们要从中取 $k$ 个数(上面说了,$k$ 不大于 $a_i$),那么有多少种方案呢?

具体证明请移步至维基百科,这里直接给出结论:
multiset
也就是 $C_{n+k-1}^{n+1}$

那么这题其实如果我们把每一行看成一个集合,元素个数就是列数-1(因为我们最终目标是走到右下角,而如果走到了右侧,再走到右下角的方案已经确定,随意等价于走到右侧),如果没有黑格子的话,我们要选的元素个数也是列数-1,答案就是 $C_{H+W-2}^{H-1}$

而如果有黑格子,我们可以统计出不合法的方案数减去即可。

所谓不合法,就是在路径上走到过黑格子,为了避免重复,我们设 $f[i]$ 为只经过第 $i$ 个黑格子的方案数,对于它的求法,可以把它当成右下角,求贡献,对于区域内的黑格子,根据乘法原理,它们产生的不合法的方案数为 $f[j]\times C_{x_i-x_j+y_i-y_j}^{x_i-x_j}$ 即原点到他的方案数乘上以第 $j$ 个黑格子为左上角,第 $i$ 个黑格子为右下角的子矩阵的方案数。

具体实现时可以按照坐标排个序,减少枚举量,设右下角为第 $n+1$ 个黑格子,方便计算答案,还有就是不要弄混横纵坐标。

代码

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注