题解 CF2247F Paths on a Grid

· · 题解

题解 CF2247F Paths on a Grid

其他题

仍然感谢@StarSilk 大神提供做法二。

题意

给定 n\times m 的 01 矩阵，保证左上和右下两格是 1。称一个非空格子集合是好的，当且仅当对于其中每个格子，从左上到右下且只往右或下走的路线中，经过该格子的所有路线都经过集合内的其他格子。求好的集合个数，对 998244353 取模。

数据范围：多测，\sum nm\le 10^6。

做法一

:::info[我毫无头绪。] 考虑能在同一好的集合内的两格应该满足什么条件。 :::

:::info[所以是什么条件？] 经过它们的路径集合相等。 :::

:::info[该如何转化？] 考虑将包含关系建边，则同一个强连通分量内可以任选，不同强连通分量间不能同时选。考虑暴力建边，但你发现边数爆了。 :::

:::info[该如何优化？] 只分别连向左上和右下离自己最近的、包含自己的格。向左上连的边和向右下连的边会分别形成一棵树。 :::

先读提示。

因为我们将边解读为集合的包含关系之后就显然有传递性，所以可以只分别连向左上和右下离自己最近的、包含自己的格。以左上为例，如果左或上只有一边能走则一定得走，直接从它连过来即可；否则从左侧格和上方格的 LCA 连过来。

这样边数是 O(nm) 的，加上算 LCA 总复杂度是 O(nm\log nm) 的。然后什么路线都到不了的点之间是任选的，要额外加一下。

这有 *2800 我吃。

做法二

前两个提示同做法一。

:::info[该如何转化？] 判断集合相等的一种常用手段是哈希。 :::

先读提示。

路径可以视为格子集合，所以首先给格子赋随机权值，然后路径就是集合哈希。然后经过一个格的路径可以分成左上、本身、右下三部分，所以从左上和右下分别开始 DP 可以分别求出左上和右下的方案数及权值和，然后乘起来就得到了完整的集合，然后随便拿点什么（比如 map）维护一下就行了。复杂度看你实现。