[蓝桥杯青少年组国赛 2025] 第六题

Luogu
IDLGB4401
Time2000ms
Memory512MB
DifficultyP4
动态规划 DP2025蓝桥杯青少年组
给定一个 $h \times w$ 的网格。机器人从左上角 $(1, 1)$ 出发,每次只能向**右**或向**下**移动一格,最终到达右下角 $(h, w)$。 网格中的每个单元格 $(i, j)$ 都有一个正整数值 $a_{i,j}$。一条路径的“乘积值”定义为该路径经过的所有单元格(包括起点和终点)的 $a_{i,j}$ 值的乘积。 你需要计算从 $(1, 1)$ 到 $(h, w)$ 且“乘积值”为 $11$ 的倍数的路径的总数。由于答案可能非常大,请将结果对 $10^9 + 7$ 取模。 ## Input 第一行包含两个整数 $h, w$,分别代表网格的高度和宽度。 接下来 $h$ 行,每行包含 $w$ 个整数,描述了整个网格。第 $i$ 行的第 $j$ 个整数代表 $a_{i,j}$ 的值。 ## Output 输出一个整数,表示符合题目要求的路径的数量,结果对 $10^9 + 7$ 取模。 [samples] ## Background 洛谷的试题为民间回忆版,仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。 本题测试数据较大,加载需要一定时间。原题内存限制为 64MB,为了鼓励更多做法,在洛谷上提供了 512MB 的内存限制。 ## Note ### 数据范围与约定 对于 100% 的数据,满足:$1 \le h, w \le 10^7$,$1 \le h \times w \le 10^7$,$1 \le a_{i,j} \le 10^9$。
Samples
Input #1
3 3
10 21 30
14 11 6
3 6 9
Output #1
4
API Response (JSON)
{
  "problem": {
    "name": "[蓝桥杯青少年组国赛 2025] 第六题",
    "description": {
      "content": "给定一个 $h \\times w$ 的网格。机器人从左上角 $(1, 1)$ 出发,每次只能向**右**或向**下**移动一格,最终到达右下角 $(h, w)$。 网格中的每个单元格 $(i, j)$ 都有一个正整数值 $a_{i,j}$。一条路径的“乘积值”定义为该路径经过的所有单元格(包括起点和终点)的 $a_{i,j}$ 值的乘积。 你需要计算从 $(1, 1)$ 到 $(h, w)$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4401"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $h \\times w$ 的网格。机器人从左上角 $(1, 1)$ 出发,每次只能向**右**或向**下**移动一格,最终到达右下角 $(h, w)$。\n\n网格中的每个单元格 $(i, j)$ 都有一个正整数值 $a_{i,j}$。一条路径的“乘积值”定义为该路径经过的所有单元格(包括起点和终点)的 $a_{i,j}$ 值的乘积。\n\n你需要计算从 $(1, 1)$ 到 $(h, w)$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments