题目大意

给定一个 $n \times m$ 的网格，要从 $(1,1)$ 走到 $(n,m)$，每次只能向下或向右走。每个格子 $(i,j)$ 有个元素值 $a_{i,j}$。定义路径的价值为：路径上不同元素的个数，求所有路径的价值之和。

---

思路

枚举所有路径并记录路径上不同元素个数的方法明显不可行且极难编码。我们可以转换思路：求对于每种元素，有多少条不同路径会经过它，也即每种元素会提供多少贡献。

对于某种元素的贡献，可以想到两种方式解决：

1. 直接计算该元素的每个点提供的贡献（容斥原理）
2. 转换思路：某种元素的贡献 = 所有贡献和 – 所有不经过该元素的贡献和（DP）

---

方式一：容斥原理（CF559C）

当某元素只有一个点 $(i,j)$ 时，贡献为：

从 $(1,1)$ 到 $(i,j)$ 的总方案数 × 从 $(i,j)$ 到 $(n,m)$ 的总方案数

而从 $(1,1)$ 到 $(i,j)$ 的总方案数，就是组合数：

$$C_{i+j-2}^{i-1}$$

因为从 $(1,1)$ 到 $(i,j)$ 一共要走 $i+j-2$ 步，其中 $i-1$ 步向下，$j-1$ 步向右，在 $i+j-2$ 步中选出 $i-1$ 步向下，其余向右。

当该元素有两个点 $(i,j)$ 和 $(x,y)$（假设 $(i,j)$ 在 $(x,y)$ 之前），那么计算 $(x,y)$ 的贡献时需要减去重复的路径。更一般地，设该元素的所有点为 $P_1, P_2, \dots, P_k$，按从左上到右下的顺序排列。定义 $f(i)$ 为：从 $(1,1)$ 到第 $i$ 个点 $P_i=(x_i,y_i)$ 且不经过同种元素其他点的方案数。

则有递推式：

$$f(i) = C_{x_i+y_i-2}^{x_i-1} - \sum_{j=1}^{i-1} \Big( f(j) \times C_{x_i+y_i-x_j-y_j}^{x_i-x_j} \Big)$$

其中 $C_{x_i+y_i-x_j-y_j}^{x_i-x_j}$ 表示从 $P_j$ 到 $P_i$ 的方案数（前提是 $P_j$ 能到达 $P_i$，即 $x_j \le x_i$ 且 $y_j \le y_i$）。

那么该元素的贡献为：

$$\sum_{i=1}^{k} \Big( f(i) \times C_{n+m-x_i-y_i}^{n-x_i} \Big)$$

这样我们枚举所有不同元素，计算其贡献并求和。若第 $i$ 种元素的数量为 $k_i$，则时间复杂度为 $O(k_i^2)$，总时间复杂度为：

$$O\left(\sum_{i=1}^{s} k_i^2 \right)$$

其中 $s$ 为不同元素种类数。

---

方式二：动态规划

对于某个元素 $x$，定义 $dp[i][j]$ 表示从 $(1,1)$ 到 $(i,j)$ 且不经过元素 $x$ 的方案数。转移方程为：

$$dp[i][j] = \begin{cases} dp[i-1][j] + dp[i][j-1], & a[i][j] \neq x \\ 0, & a[i][j] = x \end{cases}$$

计算完后，$dp[n][m]$ 就是所有不经过元素 $x$ 的路径总数。而所有路径总数为：

$$C_{n+m-2}^{n-1}$$

因此元素 $x$ 的贡献为：

$$C_{n+m-2}^{n-1} - dp[n][m]$$

枚举所有不同元素，求出它们各自的贡献并求和。若共有 $s$ 种不同元素，则时间复杂度为 $O(s \times nm)$。

---

根号分治

分析两种方式的极端情况：

• 方式一（容斥）在“不同元素少，但单个元素出现次数多”时，时间复杂度会恶化到 $O((nm)^2)$。
• 方式二（DP）在“不同元素多，但单个元素出现次数少”时，时间复杂度也会恶化到 $O((nm)^2)$。

因此我们可以取长补短：对于出现次数少的元素用容斥，出现次数多的元素用 DP。设基准值 $B = \sqrt{nm}$。

• 若某元素出现次数 $k \le \sqrt{nm}$，采用容斥原理，时间复杂度 $O(k^2)$。
• 若某元素出现次数 $k > \sqrt{nm}$，采用 DP，时间复杂度 $O(nm)$。

复杂度证明

• 对于 $k \le \sqrt{nm}$ 的元素，有：

$$\sum k_i^2 \le \max\{k_i\} \cdot \sum k_i \le \sqrt{nm} \cdot nm = O(nm\sqrt{nm})$$

• 对于 $k > \sqrt{nm}$ 的元素，这样的元素个数最多为 $\frac{nm}{\sqrt{nm}} = \sqrt{nm}$ 个，每个 DP 花费 $O(nm)$，总复杂度也为 $O(nm\sqrt{nm})$。

因此总时间复杂度稳定在：

$$O(nm\sqrt{nm})$$

这样便能在可接受的时间内解决本题。