B. 最少末尾零的路径

题目大意

给定一个 $n \times n$ 的矩阵，每个格子是一个不超过 $10^9$ 的非负整数。从左上角 $(1,1)$ 出发，每次只能向右或向下移动一格，最终到达右下角 $(n,n)$。将经过的所有数字相乘，得到的乘积末尾可能含有若干个零。要求找出一条路径，使得乘积末尾零的个数最少，并输出该最少个数及任意一条满足条件的路径（用字符 D 表示向下，R 表示向右）。

数据范围：$2 \le n \le 1000$。

---

问题分析

一个正整数末尾零的个数，取决于其质因数分解中 $2$ 的幂次和 $5$ 的幂次的较小值。即若数 $N$ 可写为：

$$N = 2^k \cdot 5^m \cdot (\text{其它质因子})$$

则末尾零的个数为 $\min(k, m)$。

对于本题，路径上所有数字的乘积可以看作每个数字质因数分解后对应幂次的累加。因此，乘积中因子 $2$ 的总个数 $K$ 等于路径上各数因子 $2$ 个数之和，因子 $5$ 的总个数 $M$ 等于路径上各数因子 $5$ 个数之和。末尾零的个数即为 $\min(K, M)$。

于是问题转化为：在网格图中找到一条从左上到右下的路径，分别使得路径上数字的因子 $2$ 总个数 $K$ 最小，以及因子 $5$ 总个数 $M$ 最小。记这两个最小值分别为 $k_1$ 和 $m_1$，则最优答案的一个上界是 $\min(k_1, m_1)$。

下界证明：若存在某条路径其末尾零个数小于 $\min(k_1, m_1)$，则该路径对应的 $K < k_1$ 或 $M < m_1$，这与 $k_1$ 和 $m_1$ 分别为最小可能值矛盾。因此 $\min(k_1, m_1)$ 即为不含零情况下的最优答案。

---

解题思路

1. 不含零的矩阵

对于每个格子，我们计算其数值中因子 $2$ 的个数 $c_2$ 和因子 $5$ 的个数 $c_5$，得到两个权值矩阵 $W_2$ 和 $W_5$。

分别对两个权值矩阵进行动态规划：

• 设 $dp2[i][j]$ 表示从 $(1,1)$ 到 $(i,j)$ 的路径上 $c_2$ 之和的最小值。
• 设 $dp5[i][j]$ 表示从 $(1,1)$ 到 $(i,j)$ 的路径上 $c_5$ 之和的最小值。

由于每次只能向右或向下移动，状态转移方程为：

$$dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1]) + w[i][j] $$

其中 $w[i][j]$ 为对应权值（$c_2$ 或 $c_5$）。边界条件为 $dp[1][1] = w[1][1]$，第一行只能从左侧转移，第一列只能从上方转移。

进行两次 DP 后，得到终点处的两个最小值 $k_1 = dp2[n][n]$ 和 $m_1 = dp5[n][n]$。最优答案即为 $\min(k_1, m_1)$。若 $k_1 \le m_1$，则选择使 $2$ 的个数最小的路径；否则选择使 $5$ 的个数最小的路径。利用 DP 过程中记录的转移方向即可回溯出具体路径。

2. 矩阵中含有零的情况

若矩阵中存在值为 $0$ 的格子，则任何经过 $0$ 的路径乘积均为 $0$，此时乘积末尾至少有一个零（事实上，数学上 $0$ 的末尾零个数通常认为是 $1$ 或无穷，本题采用 $1$ 处理）。

按照题解建议的方法：

• 首先将所有 $0$ 替换为 $10$（因为 $10 = 2 \times 5$，含有一个 $2$ 和一个 $5$）。
• 对替换后的矩阵应用上述不含零矩阵的 DP 算法，得到最优值 $best = \min(k_1, m_1)$。
• 若 $best = 0$，说明存在一条完全不经过 $0$ 的路径，且其乘积末尾没有零，此时直接采用该路径。
• 若 $best > 0$（或原本就不存在不含零的路径），则说明任意一条不经过 $0$ 的路径末尾零个数都至少为 $1$，此时我们可以构造一条经过任意一个 $0$ 的路径，其乘积为 $0$，末尾零个数计为 $1$，这显然是最优的（不可能得到 $0$ 个零）。

经过 $0$ 的路径构造非常简单：从起点走到该 $0$ 所在位置，再从该位置走到终点即可。由于每一步只能向右或向下，这样的路径一定存在。

3. 路径还原

在 DP 过程中，我们使用一个字符矩阵 $path$ 记录每个格子的前驱方向。例如：

• 若 $dp[i][j]$ 由 $dp[i-1][j]$ 转移而来，则记录 $path[i][j] =$ 'D'；
• 若由 $dp[i][j-1]$ 转移而来，则记录 'R'。

从终点 $(n,n)$ 开始，不断根据记录的方向回退至起点，将得到的方向序列反转即为从起点到终点的正确路径。

---

复杂度分析

• 计算每个数的因子个数：对于每个数需要 $O(\log \text{value})$ 的时间，矩阵共有 $n^2$ 个数，总时间 $O(n^2 \log M)$，其中 $M \le 10^9$。
• 两次动态规划：每次需要遍历整个 $n \times n$ 矩阵，时间复杂度 $O(n^2)$。
• 路径回溯：$O(n)$。

总时间复杂度为 $O(n^2 \log M)$，在 $n \le 1000$ 时完全可以接受。空间复杂度为 $O(n^2)$，用于存储 DP 数组和路径记录。

---

标程（C++）

#include <bits/stdc++.h>
using namespace std;

int countFactor(int x, int p) {
    int cnt = 0;
    while (x % p == 0) {
        cnt++;
        x /= p;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));

    bool hasZero = false;
    int zeroX = -1, zeroY = -1;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 0) {
                if (!hasZero) {
                    hasZero = true;
                    zeroX = i;
                    zeroY = j;
                }
                a[i][j] = 10;   // 替换 0 为 10
            }
        }
    }

    // 因子矩阵
    vector<vector<int>> twos(n, vector<int>(n));
    vector<vector<int>> fives(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            twos[i][j] = countFactor(a[i][j], 2);
            fives[i][j] = countFactor(a[i][j], 5);
        }
    }

    // DP for 2's
    vector<vector<int>> dp2(n, vector<int>(n));
    vector<vector<char>> path2(n, vector<char>(n));
    dp2[0][0] = twos[0][0];
    path2[0][0] = 'S'; // start
    for (int i = 1; i < n; ++i) {
        dp2[i][0] = dp2[i-1][0] + twos[i][0];
        path2[i][0] = 'D';
    }
    for (int j = 1; j < n; ++j) {
        dp2[0][j] = dp2[0][j-1] + twos[0][j];
        path2[0][j] = 'R';
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            if (dp2[i-1][j] <= dp2[i][j-1]) {
                dp2[i][j] = dp2[i-1][j] + twos[i][j];
                path2[i][j] = 'D';
            } else {
                dp2[i][j] = dp2[i][j-1] + twos[i][j];
                path2[i][j] = 'R';
            }
        }
    }

    // DP for 5's
    vector<vector<int>> dp5(n, vector<int>(n));
    vector<vector<char>> path5(n, vector<char>(n));
    dp5[0][0] = fives[0][0];
    path5[0][0] = 'S';
    for (int i = 1; i < n; ++i) {
        dp5[i][0] = dp5[i-1][0] + fives[i][0];
        path5[i][0] = 'D';
    }
    for (int j = 1; j < n; ++j) {
        dp5[0][j] = dp5[0][j-1] + fives[0][j];
        path5[0][j] = 'R';
    }
    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            if (dp5[i-1][j] <= dp5[i][j-1]) {
                dp5[i][j] = dp5[i-1][j] + fives[i][j];
                path5[i][j] = 'D';
            } else {
                dp5[i][j] = dp5[i][j-1] + fives[i][j];
                path5[i][j] = 'R';
            }
        }
    }

    int k1 = dp2[n-1][n-1];
    int m1 = dp5[n-1][n-1];
    int best = min(k1, m1);

    // 情况1：无零 或 最优非零路径尾零个数为0
    if (!hasZero || best == 0) {
        cout << best << "\n";
        const auto& path = (k1 <= m1) ? path2 : path5;
        string way;
        int x = n-1, y = n-1;
        while (x != 0 || y != 0) {
            char dir = path[x][y];
            way.push_back(dir);
            if (dir == 'D') x--;
            else y--;
        }
        reverse(way.begin(), way.end());
        cout << way << "\n";
        return 0;
    }

    // 情况2：含零且所有非零路径尾零个数均≥1
    cout << 1 << "\n";
    string way;
    for (int i = 0; i < zeroX; ++i) way.push_back('D');
    for (int j = 0; j < zeroY; ++j) way.push_back('R');
    for (int i = zeroX; i < n - 1; ++i) way.push_back('D');
    for (int j = zeroY; j < n - 1; ++j) way.push_back('R');
    cout << way << "\n";

    return 0;
}