P8559 寻宝（Treasure）

NaCly_Fish · 2022-10-06 08:12:41 · 题解

以下复杂度分析中，均认为 n,k,m 同阶。

题目中给出的「恰好 m 个宝物」的条件有点难处理，先考虑一个简化的问题：求 2\times n 的网格中放置 k 个障碍物，使得最左侧和最右侧连通的方案数。

设 a_{n,k} 为放置 k 个障碍物，且最右侧两格不放障碍，使得最左侧和最右侧连通的方案数；类似地设 b_{n,k}，要求最右侧放一个障碍。

我们很快就能得到递推式（注意 a_{0,0}=1）：

现在来考虑原问题，枚举和左边连通的块的最右端在哪，要注意的是和左边连通的块被截断时，会有三种情况：

对于情况 A，截断连通块需要 2 个障碍，右侧还有 2\times(n-i-1) 个格子，可以随便放上 k-(2i-m)-2 个障碍；而 B、C 两种情况是等价的，可以类比情况 A 来推出答案为：

那个单独的项是因为地图的边界也是障碍，不需要放额外的障碍来截断。

当然我们不满足于 \Theta(n^2) 递推计算 a_{i,2i-m}，注意到求和式中实际只用到了 \Theta(m) 个 a 的值，而且都是在一条斜线上的。为了找出可能的优化算法，我们尝试对 m\geq 2 列出所有 a_{i,2i-m} 非零项的值，再把每行翻转一下，得到了这样一个三角形：

1 
2
2 1
2 4
2 8 1
2 12 6
2 16 18 1
2 20 38 8
2 24 66 32 1

设其中第 m 行（从 0 开始计）的生成函数为 F_m(x)，将原始递推式化简为 a_{n,k}=a_{n-2,k-1}+a_{n-1,k-1}+a_{n-1,k}，映射到这个三角形上就是 F_m(x)=F_{m-1}(x)+xF_{m-2}(x)+xF_{m-3}(x)。

如果设其中第 k 列（从 1 开始计）的生成函数为 C_k(x)，就有：

使用经典方法，设