「COCI 2023.1」Bomboni 题解

题目大意

给定一个 $n \times n$ 的网格，Iva 从左上角 $(1,1)$ 出发，只能向右或向下移动到右下角 $(n,n)$。每个格子要么是障碍物（值为 $-1$），要么有一个正整数糖果值。Iva 会收集路径上所有糖果，并计算它们的乘积。问有多少条路径的糖果乘积能被 $k$ 整除，结果对 $998244353$ 取模。

解题思路

关键观察

1. 乘积整除性：路径乘积能被 $k$ 整除 ⇔ 乘积与 $k$ 的最大公约数等于 $k$
2. 动态规划状态：维护到每个格子 $(i,j)$ 时，路径乘积与 $k$ 的 GCD 值及其对应方案数
3. 状态压缩：GCD 值一定是 $k$ 的约数，状态数不会太多

算法核心

状态设计

定义 $D[i][j][g]$ 表示从起点 $(1,1)$ 到格子 $(i,j)$ 的所有路径中，路径乘积与 $k$ 的最大公约数为 $g$ 的方案数。

状态转移

对于每个格子 $(i,j)$（非障碍物）：

• 从上方 $(i-1,j)$ 转移：$D[i][j][\text{gcd}(g \times A[i][j], k)] += D[i-1][j][g]$
• 从左方 $(i,j-1)$ 转移：$D[i][j][\text{gcd}(g \times A[i][j], k)] += D[i][j-1][g]$

空间优化

使用滚动数组，只保留当前行和上一行的状态。

代码解析

#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (a); i <= (int)(b); ++i)
using LL = long long;

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

const int NN = 504;
using MI = unordered_map<int, int>;
using VL = vector<LL>;
MI D[2][NN];  // 滚动数组：D[行奇偶][列][GCD值] = 方案数

int main() {
    const int MD = 998244353;
    int n, k;
    cin >> n >> k;
    vector<VL> A(n + 1, VL(n + 1));
    REP(i, 1, n) REP(j, 1, n) cin >> A[i][j];
    
    // 计算新GCD的辅助函数
    auto gk = [&](LL a) {
        return gcd(a, k);
    };
    
    // 初始化起点
    D[1][1][gk(A[1][1])] = 1;
    
    // 动态规划主循环
    REP(i, 1, n) REP(j, 1, n) {
        if (i == 1 && j == 1) continue;
        
        int ci = i % 2;        // 当前行索引
        int a = A[i][j];       // 当前格子值
        int i1 = ci ^ 1;       // 上一行索引
        auto &d = D[ci][j];    // 当前状态引用
        d.clear();             // 清空当前状态
        
        if (a < 0) continue;   // 跳过障碍物
        
        // 从上方转移
        if (i > 1) {
            for (const auto &p : D[i1][j]) {
                LL new_g = gk(LL(p.first) * a);
                d[new_g] = (d[new_g] + p.second) % MD;
            }
        }
        
        // 从左方转移  
        if (j > 1) {
            for (const auto &p : D[ci][j - 1]) {
                LL new_g = gk(LL(p.first) * a);
                d[new_g] = (d[new_g] + p.second) % MD;
            }
        }
    }
    
    // 输出结果：终点处GCD等于k的方案数
    cout << D[n % 2][n][k] << endl;
    return 0;
}

算法正确性

为什么这样设计？

• GCD 的传递性：$\text{gcd}(a \times b, k) = \text{gcd}(\text{gcd}(a,k) \times b, k)$
• 状态合并：不同路径可能产生相同的 GCD 值，可以合并计数
• 最终答案：$D[n][n][k]$ 表示终点处 GCD 恰好为 $k$ 的方案数

复杂度分析

• 时间复杂度：$O(n^2 \cdot d(k))$，其中 $d(k)$ 是 $k$ 的约数个数
• 空间复杂度：$O(n \cdot d(k))$，使用滚动数组优化

样例验证

样例1

n=2, k=2
网格：
3 2
1 4

路径1：3→2→1→4，乘积=24，GCD(24,2)=2 ✓
路径2：3→2→4，乘积=24，GCD(24,2)=2 ✓
输出：2 ✓

样例2

n=3, k=6  
网格：
5  2 -1
7  3  6
-1 3  1

输出：3 ✓

总结

本题的巧妙解法在于：

1. GCD 状态压缩：利用 GCD 值作为状态，避免直接维护大数乘积
2. 约数个数有限：$k \leq 10^6$ 的约数个数不会太多（实际约 $200$ 个）
3. 滚动数组优化：将空间复杂度从 $O(n^2 \cdot d(k))$ 降到 $O(n \cdot d(k))$

这种基于 GCD 的状态设计对于处理乘积整除性问题具有很好的通用性。