AT_joi2022_yo2_c.国土分割 (Land Division)

JOI 国的国土呈长方形，被划分为纵向 $H$ 行、横向 $W$ 列的格子。JOI 国的纵向与南北方向平行，横向与东西方向平行。从北往南第 $i$ 行（$1 \leq i \leq H$）、从西往东第 $j$ 列（$1 \leq j \leq W$）的格子里住有 $A_{i,j}$ 人。

为了提高行政效率，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 \leq H \leq 50$。
• $1 \leq W \leq 50$。
• $1 \leq A_{i,j} \leq 100\,000$（$1 \leq i \leq H$，$1 \leq j \leq W$）。
• 输入的所有数值均为整数。

子任务

1.（12 分）$H = 1$。
2.（26 分）$H \leq 6$，$W \leq 6$。
3.（62 分）无额外约束。

评测说明

所有提交将在评测系统上进行评分。

提交的源代码在对应子任务的所有评测输入数据上都输出正确结果时，才算该子任务通过。

每次提交的得分为通过的所有子任务的得分之和。

本题的得分为所有提交中得分的最大值。

当前得分可在“提交结果”标签页的“我的得分情况”中查看。

样例解释 1

如下图所示，使所有地区人口相等的分割方法有 $3$ 种，因此输出 $3$。



该输入样例满足子任务 $2,3$ 的约束。

样例解释 2

如下图所示，使所有地区人口相等的分割方法有 $2$ 种，因此输出 $2$。


该输入样例满足所有子任务的约束。

样例解释 3

如下图所示，使所有地区人口相等的分割方法有 $2$ 种，因此输出 $2$。


该输入样例满足子任务 $2,3$ 的约束。

样例解释 4

不存在使所有地区人口相等的分割方法，因此输出 $0$。
该输入样例满足所有子任务的约束。

由 ChatGPT 4.1 翻译