P14327 [JOI2022 预选赛 R2] 国土分割 / Land Division
题目描述
JOI 国呈矩形，被划分为 $ H $ 行 $ W $ 列的网格状区域。JOI 国的纵向与南北方向平行，横向与东西方向平行。从北往南第 $ i $ 行（$ 1 \le i \le H $）、从西往东第 $ j $ 列（$ 1 \le j \le W $）的格子人口为 $ A_{ij} $ 人。
为提升行政效率，JOI 国决定通过绘制一条或多条边界线，将全国划分为两个或以上的区域。边界线需满足以下条件：
- 边界线必须位于网格的边界上。
- 边界线必须是从 JOI 国北端到南端，或从东端到西端的连续线段。
已知 JOI 国每个格子的人口数，编写程序，计算在所有可能的划分方案中，能使各个区域人口相等的划分方法共有多少种。
输入格式
输入通过标准输入以如下格式给出：
$ H $ $ W $
$ A_{1,1} $ $ A_{1,2} $ $ \cdots $ $ A_{1,W} $
$ A_{2,1} $ $ A_{2,2} $ $ \cdots $ $ A_{2,W} $
$ \vdots $
$ A_{H,1} $ $ A_{H,2} $ $ \cdots $ $ A_{H,W} $
输出格式
在标准输出中，以单行输出能使所有区域人口相等的划分方法的总数。
说明/提示
### 样例 1 解释
下图解释了样例 1 的三种方式：
:::align{center}
:::
### 样例 2 解释
下图解释了样例 2 的两种方式：
:::align{center}
:::
### 样例 3 解释
下图解释了样例 3 的两种方式：
:::align{center}
:::
### 数据范围
- $ 1 \le H \le 50 $。
- $ 1 \le W \le 50 $。
- $ 1 \le A_{ij} \le 100\,000 $（$ 1 \le i \le H $，$ 1 \le j \le W $）。
- 所有输入值均为整数。
### 子任务
1. （12 分）$ H = 1 $。
2. （26 分）$ H \le 6 $，$ W \le 6 $。
3. （62 分）无额外约束。
翻译由 Qwen3-235B 完成