← 返回题目列表

AtCoder · joi2022_yo2_c

C. 土地划分

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI国纵 H 行,横 W 它具有矩形形状,分为多个列网格。 JOI国家的纵向与南北方向平行,横向与东西方向平行。从北方 i 行目 (1 \leqq i \leqq H),从西边 j 列目 (1 \leqq j \leqq W) 中的方格数量为 A_{i,j} 这是一个人。

在JOI国家中,设立满足以下条件的边界以提高行政效率。 1 通过绘制多本书,整个国家都可以 2 我们决定将其划分为多个区。

  • 边界线位于网格的边界上。
  • 边界线是连接 JOI 国家北端与南端,或连接 JOI 国家东端与西端的线段。

JOI 给定全国每个方格的人口,编写一个程序,找出有多少种划分方法,可以使所有地区的人口在可能的划分方法中相等。

制約

  • 1 \leqq H \leqq 50.
  • 1 \leqq W \leqq 50.
  • 1 \leqq A_{i,j} \leqq 100\,000 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  • 所有输入值都是整数。

小課題

  1. (12 点) H = 1.
  2. (26 点) H \leqq 6,W \leqq 6.
  3. (62 点)没有额外的限制。

评分注意事项

所有提交的内容都将通过评审系统进行评分。

如果提交的源代码为与该子作业对应的所有评分输入数据返回正确的结果,则该源代码将被识别为对于该子作业是正确的。

每次提交的分数是所提交源代码被认为正确的子任务分数的总和。

该作业的分数是此作业所有提交的最高分。

您可以在“提交结果”选项卡上的“我的分数状态”中查看您当前的分数。


入力

输入是按以下格式从标准输入给出的。

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

2 3
10 10 20
10 10 20

出力例 1

3

如下图所示,使各区人口相等的划分方法为 3 因为有途径, 输出3 。

此输入示例是一个小作业。 2,3 满足约束。


入力例 2

1 4
2 1 1 2

出力例 2

2

如下图所示,使各区人口相等的划分方法为 2 因为有途径, 输出2 。

此输入示例满足所有子任务约束。


入力例 3

3 3
2 9 4
7 5 3
6 1 8

出力例 3

2

如下图所示,使各区人口相等的划分方法为 2 因为有途径, 输出2 。

此输入示例是一个小作业。 2,3 满足约束。


入力例 4

1 1
10000

出力例 4

0

由于没有一种划分方法可以使所有地区的人口相等,0 。

此输入示例满足所有子任务约束。