梦境世界

Luogu

IDLGP10027

Time2000ms

Memory512MB

DifficultyP5

动态规划 DP洛谷原创O2优化洛谷月赛

有一个长为 $n$ 宽为 $m$ 的网格，其左上角编号为位置 $(1, 1)$ 而右下角编号为位置 $(n, m)$。哆来咪想要从左上角走到右下角，每次她可以往右或向下走一格，但不能超出 $n\times m$ 的网格边界。除此之外，有 $s$ 个禁止点是哆来咪无法走到的。哆来咪有 $k$ 个神奇药水，喝药水可以撤销之前最后一次没有被撤销的行走操作，但移动序列并不会删去最后一个元素。当然，在 $(1, 1)$ 位置时不能使用药水，且 **药水不会撤销上一个药水的操作**。例如：从 $A$ 到 $B$ 后，在 $B$ 处喝了药水，则移动序列为 $A \to B \to A$；从 $A$ 走到 $B$ 再走到 $C$，连续喝下两次药水，移动序列为 $A \to B \to C \to B \to A$。哆来咪认为一次 **旅行** 是指一次最终走到 $(n, m)$ 的行走路线。哆来咪想要求本质不同的 **旅行** 个数，答案对给定 $p$ 取模。哆来咪认为两次 **旅行** 不同，当且仅当两次旅行记录的移动序列不同。 ## Input 第一行五个整数 $n, m, k, p, s$，意义见题目描述。接下来 $s$ 行，第 $i$ 行包含两个整数 $(x_i, y_i)$，表示不能经过网格中编号为 $(x_i, y_i)$ 的点。 ## Output 输出一行一个整数，表示答案对 $p$ 取模后的结果。 [samples] ## Background 哆来咪爱旅行。 ## Note ### 样例解释 1 七种路线如下： ![](https://cdn.luogu.com.cn/upload/image_hosting/0t9so91p.png) ### 数据规模与约定 **本题采用捆绑测试。** - Subtask 0（10pts）：$1 \le n, m \le 100$，$k=0$。 - Subtask 1（15pts）：$1 \le n, m \le 10$，$k=1$。 - Subtask 2（15pts）：$n=1$，$m \le 100$，$k \le 100$。 - Subtask 3（25pts）：$1 \le n, m \le 100$，$k \le 10$。 - Subtask 4（35pts）：无特殊限制。对于所有数据，保证 $1 \le n, m \le 100$，$0 \le k \le 100$，$2 \le p \le 10^9 + 9$，$0 \le s \le n \times m$，$1 \le x_i \le n$，$1 \le y_i \le m$，且 $(x_i, y_i)$ 互不相同。

Samples

Input #1

2 2 2 998244353 1
1 2

Output #1

Input #2

5 5 0 114514 0

Output #2

Input #3

5 5 3 998244353 3
3 4
2 5
4 4

Output #3

API Response (JSON)

{
  "problem": {
    "name": "梦境世界",
    "description": {
      "content": "有一个长为 $n$ 宽为 $m$ 的网格，其左上角编号为位置 $(1, 1)$ 而右下角编号为位置 $(n, m)$。哆来咪想要从左上角走到右下角，每次她可以往右或向下走一格，但不能超出 $n\\times m$ 的网格边界。除此之外，有 $s$ 个禁止点是哆来咪无法走到的。 哆来咪有 $k$ 个神奇药水，喝药水可以撤销之前最后一次没有被撤销的行走操作，但移动序列并不会删去最后一个元素。当然，在 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10027"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个长为 $n$ 宽为 $m$ 的网格，其左上角编号为位置 $(1, 1)$ 而右下角编号为位置 $(n, m)$。哆来咪想要从左上角走到右下角，每次她可以往右或向下走一格，但不能超出 $n\\times m$ 的网格边界。除此之外，有 $s$ 个禁止点是哆来咪无法走到的。\n\n哆来咪有 $k$ 个神奇药水，喝药水可以撤销之前最后一次没有被撤销的行走操作，但移动序列并不会删去最后一个元素。当然，在 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments