「CGOI-2」No cost too great

Luogu
IDLGP8502
Time1000ms
Memory256MB
DifficultyP5
动态规划 DPO2优化容斥原理差分
白王正在最后一次参观他建造的宏伟宫殿。现在假设宫殿由 $n$ 个房间构成，房间之间有若干个**单向**通道。出于白王奇怪的装修癖好（不是指到处安电锯），对于第 $i$ 个房间，它向编号在区间 $[l_i,r_i]$ 中的所有房间都连有一条单向通道。例如，$4$ 号房间向 $[2,5]$ 连有单向通道，就意味着从 $4$ 号房间到 $2,3,4,5$ 号房间各有一条单向通道（一个房间可以向自己连有通道）。当一个房间向 $[0,0]$ 连有通道时，表示没有从这个房间出发的通道。 白王提出了 $q$ 个问题，每次询问从 $a$ 号房间，通过恰好 $m$ 条单向通道且不经过 $c$ 号房间到达 $b$ 号房间的方案数（两方案不同，当且仅当存在 $i$ 使得两方案通过的第 $i$ 条通道不同）。因为这个数字可能会很大，所以白王让你将答案模 $998244353$ 后再回答。 ## Input 第一行，两个整数 $n, q$ 表示点数和询问数。 接下来 $n$ 行，每行两个整数 $l, r$，第 $i+1$ 行的整数 $l_i, r_i$ 表示 $i$ 号节点向区间 $[l_i, r_i]$ 中的每个点都连了一条单向边。当 $l_i=r_i=0$ 时，表示该节点没有向任何点连边。 接下来 $q$ 行，每行四个整数 $a, b, c, m$ 表示一个询问。 ## Output $q$ 行，每行一个整数，第 $i$ 行的数字表示第 $i$ 个询问的方案数模 $998244353$ 的结果。 [samples] ## Background 光芒浸透圣巢，她正犯下弥天之错。 所剩寥寥无几的信仰，为什么始终执着。 我将作灯塔，照耀王国。 但在那之前有更重要的事去做， 无论什么代价都在所不惜，尽管我所剩无多…… ## Note ### 样例说明 在样例一中，$1$ 号房间能到达 $2,3$ 号房间，$2$ 号房间能到达 $1$ 号房间，$3$ 号房间能到达 $2,3,4$ 号房间，$4$ 号房间不能到达任何房间。 对于第一个询问，从 $1$ 号房间经过 $5$ 条通道且不经过 $4$ 号房间到达 $3$ 号房间的方案有 `121213`，`121333`，`133213`，`132133`，`133333` 共五种。 --- ### 数据范围 **本题采用捆绑测试。** | 编号| 特殊性质 | 空间限制 |分数 | | :-: | :-: | :-: | :-: | | 0 | $n\le10$，$q\le10$，$m\le4$ | 256MB | 10pts | | 1 | $n\le100$，$q\le10^4$，$m\le40$ | 256MB | 15pts | | 2 | 对于所有询问，$l_c=r_c=0$ | 256MB | 15pts | | 3 | 无 | 256MB | 30pts | | 4 | 无 | 128MB | 30pts | 对于 $100\%$ 的数据，$1\le n \le 500$，$1\le q \le 10^5$，$1\le m \le 100$，$0 \le l_i \le r_i \le n$，$1 \le a,b,c \le n$。当且仅当 $l_i=0$ 时 $r_i=0$。时间限制均为 1s。 --- ### 提示 **注意空间常数。**
Samples
Input #1
4 5
2 3
1 1
2 4
0 0
1 3 4 5
1 4 2 4
2 3 1 2
4 4 3 0
1 3 2 5
Output #1
5
1
0
1
1
Input #2
10 10
6 6
4 10
2 5
1 7
3 4
5 7
4 10
1 7
1 3
2 5
8 8 5 1
4 7 5 3
5 9 4 4
1 5 5 2
6 2 10 2
3 3 7 4
1 10 1 2
6 2 4 4
9 2 1 4
9 10 3 2
Output #2
0
17
2
0
0
46
0
12
23
1
Input #3
10 10
2 6
6 9
5 7
3 9
0 0
0 0
3 5
5 5
3 6
1 10
5 9 6 3
10 8 6 4
10 8 5 1
8 6 5 4
7 2 5 4
6 1 5 3
10 4 5 1
5 5 6 0
7 9 6 4
4 9 6 2
Output #3
0
17
1
0
0
0
1
1
4
1
API Response (JSON) 
{
  "problem": {
    "name": "「CGOI-2」No cost too great",
    "description": {
      "content": "白王正在最后一次参观他建造的宏伟宫殿。现在假设宫殿由 $n$ 个房间构成，房间之间有若干个**单向**通道。出于白王奇怪的装修癖好（不是指到处安电锯），对于第 $i$ 个房间，它向编号在区间 $[l_i,r_i]$ 中的所有房间都连有一条单向通道。例如，$4$ 号房间向 $[2,5]$ 连有单向通道，就意味着从 $4$ 号房间到 $2,3,4,5$ 号房间各有一条单向通道（一个房间可以向自己连有通",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8502"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "白王正在最后一次参观他建造的宏伟宫殿。现在假设宫殿由 $n$ 个房间构成，房间之间有若干个**单向**通道。出于白王奇怪的装修癖好（不是指到处安电锯），对于第 $i$ 个房间，它向编号在区间 $[l_i,r_i]$ 中的所有房间都连有一条单向通道。例如，$4$ 号房间向 $[2,5]$ 连有单向通道，就意味着从 $4$ 号房间到 $2,3,4,5$ 号房间各有一条单向通道（一个房间可以向自己连有通...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac