CF 2B

The least round way

Description

有一个 n × n 的正方形矩阵，由非负整数组成。请你找到一条路径符合以下条件：

• 从矩阵的左上角出发
• 每次只能往右或者往下走
• 最终达到矩阵的右下角

除此之外，如果我们把路径上的数相乘，结果必须包含最少的后缀零。

Input

第一行输入一个整数 n (2 ≤ n ≤ 1000)，表示矩阵的大小。以下 n 行，每行 n 个数，依次输入矩阵里的非负整数（不超过 10⁹）。

Output

第一行输出一个整数，表示最少的后缀零个数。 第二行输出对应的路径。

Solution

我们可以根据一个数的因子含有多少个 10 来判断一个数末尾有多少个零。同时，因为 10 可以分解成两个质数 10 = 5 × 2，所以只需要算出，路径上所有数乘积的质因子中，包含了多少个 5 和多少个 2，则 5 和 2 中最少的数字决定了 10 的个数。

知道了这个基本的数论知识后，我们便可以 DP 求解这道题。但是一开始思考时，容易陷入误区，把状态设为走到了某个格子上之后，乘积中包含因子 2 或 5 最少的有几个，仔细一想，便可以发现这样会具有后效性。正确的做法应该是，分别计算到某个格子上，乘积中包含因子 2 最少有几个和 5 最少有几个。最后的答案便是右下角的格子上，因数 2 的个数和 5 的个数中的最小值。由此转化成了一道经典的 DP 题。

最后还要注意一点，矩形中包含的是非负整数，因此，0 也会出现在矩阵中。由于 0 和任何数相乘，都为 0，只包含了一个后缀零。所以，当前面计算的结果（不经过 0）大于 1，并且矩阵中包含数字 0 的时候。正确的路径，应该是经过 0 的任意一条路。