{"problem":{"name":"「TAOI-1」Pentiment","description":{"content":"我们规定，在 $n$ 行 $m$ 列的网格中，“直角蛇”是这样一条路径： - 从最下方（第一行）的某个格子的中心开始，在最上方（第 $n$ 行）的某个格子的中心结束。 - 每次可以向上、向右或向左移动一格，每次移动后都到达某个格子的中心（**不能向下移动**）。 - 不能重复经过同一个格子。 特别地，为了给你增加一些考验，我们规定有一些格子是“直角蛇”不能经过的。 请你统计在给定的网格中存在","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9221"},"statements":[{"statement_type":"Markdown","content":"我们规定，在 $n$ 行 $m$ 列的网格中，“直角蛇”是这样一条路径：\n\n- 从最下方（第一行）的某个格子的中心开始，在最上方（第 $n$ 行）的某个格子的中心结束。\n- 每次可以向上、向右或向左移动一格，每次移动后都到达某个格子的中心（**不能向下移动**）。\n- 不能重复经过同一个格子。\n\n特别地，为了给你增加一些考验，我们规定有一些格子是“直角蛇”不能经过的。\n\n请你统计在给定的网格中存在多少种这样的“直角蛇”。答案对 $998244353$ 取模。\n\n## Input\n\n第一行三个整数 $n, m, q$，代表网格的行数和列数，以及限制的数量。\n\n接下来的 $q$ 行，每行两个整数 $x_i, y_i$，代表第 $x_i$ 行第 $y_i$ 列的格子不能经过。保证同一个格子至多出现一次。保证所有格子按照 $x_i$ 为第一关键字，$y_i$ 为第二关键字，从小到大排序后给出。（我们规定最下方的格子的行数为 $1$，最左侧格子的列数为 $1$）\n\n## Output\n\n共一行一个整数，代表符合条件的“直角蛇”数量对 $998244353$ 取模的结果。\n\n[samples]\n\n## Background\n\n近日（存疑），一款名为闊靛緥婧愮偣的游戏更新了它的 4.0 版本。在这个版本中某谱面中的大直角蛇给玩家们留下了深刻的印象……\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qbdvtftu.png)\n\n## Note\n\n### 数据范围\n\n**本题采用捆绑测试**。\n\n- Subtask 1（10 points）：$n \\leq 10^6$，$m \\leq 2$。\n- Subtask 2（10 points）：$q=0$。\n- Subtask 3（15 points）：$n,m \\leq 10^4$。\n- Subtask 4（20 points）：$n \\leq 10^4$。\n- Subtask 5（20 points）：$m \\leq 10^4$。\n- Subtask 6（25 points）：无特殊限制。\n\n对于所有测试数据，$2 \\leq n \\leq 10^9$，$1 \\leq m \\leq 10^9$，$0 \\leq q \\leq 10^5$，$1 \\leq x_i \\leq n$，$1 \\leq y_i \\leq m$。\n\n### 样例解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/dkyhh41q.png)\n\n如图，样例一中共有八种满足条件的“直角蛇”。\n\n对于样例二，不存在满足条件的“直角蛇”。\n\n---\n\n在寂若死灰中屈服。\n\n在飘忽不定中屈服。\n\n在功亏一篑中屈服。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9221","tags":["动态规划 DP","线段树","颜色段均摊（珂朵莉树 ODT）","O2优化"],"sample_group":[["2 3 2\n1 1\n2 1","8"],["4 4 4\n1 1\n2 2\n3 3\n4 4","0"],["6 5 4\n1 3\n3 1\n3 4\n5 2","2000"],["100000000 100000000 0","103866487"]],"created_at":"2026-03-03 11:09:25"}}