{"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$ 号房间各有一条单向通道（一个房间可以向自己连有通道）。当一个房间向 $[0,0]$ 连有通道时，表示没有从这个房间出发的通道。\n\n白王提出了 $q$ 个问题，每次询问从 $a$ 号房间，通过恰好 $m$ 条单向通道且不经过 $c$ 号房间到达 $b$ 号房间的方案数（两方案不同，当且仅当存在 $i$ 使得两方案通过的第 $i$ 条通道不同）。因为这个数字可能会很大，所以白王让你将答案模 $998244353$ 后再回答。\n\n## Input\n\n第一行，两个整数 $n, q$ 表示点数和询问数。\n\n接下来 $n$ 行，每行两个整数 $l, r$，第 $i+1$ 行的整数 $l_i, r_i$ 表示 $i$ 号节点向区间 $[l_i, r_i]$ 中的每个点都连了一条单向边。当 $l_i=r_i=0$ 时，表示该节点没有向任何点连边。\n\n接下来 $q$ 行，每行四个整数 $a, b, c, m$ 表示一个询问。\n\n## Output\n\n$q$ 行，每行一个整数，第 $i$ 行的数字表示第 $i$ 个询问的方案数模 $998244353$ 的结果。\n\n[samples]\n\n## Background\n\n光芒浸透圣巢，她正犯下弥天之错。\n\n所剩寥寥无几的信仰，为什么始终执着。\n\n我将作灯塔，照耀王国。\n\n但在那之前有更重要的事去做，\n\n无论什么代价都在所不惜，尽管我所剩无多……\n\n## Note\n\n### 样例说明\n\n在样例一中，$1$ 号房间能到达 $2,3$ 号房间，$2$ 号房间能到达 $1$ 号房间，$3$ 号房间能到达 $2,3,4$ 号房间，$4$ 号房间不能到达任何房间。\n\n对于第一个询问，从 $1$ 号房间经过 $5$ 条通道且不经过 $4$ 号房间到达 $3$ 号房间的方案有 `121213`，`121333`，`133213`，`132133`，`133333` 共五种。\n\n---\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n| 编号| 特殊性质 | 空间限制 |分数 |\n| :-: | :-: | :-: | :-: |\n| 0 | $n\\le10$，$q\\le10$，$m\\le4$ | 256MB | 10pts |\n| 1 | $n\\le100$，$q\\le10^4$，$m\\le40$ | 256MB | 15pts |\n| 2 | 对于所有询问，$l_c=r_c=0$ | 256MB | 15pts |\n| 3 | 无 | 256MB | 30pts |\n| 4 | 无 | 128MB | 30pts |\n\n对于 $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。\n\n---\n\n### 提示\n\n**注意空间常数。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8502","tags":["动态规划 DP","O2优化","容斥原理","差分"],"sample_group":[["4 5\n2 3\n1 1\n2 4\n0 0\n1 3 4 5\n1 4 2 4\n2 3 1 2\n4 4 3 0\n1 3 2 5","5\n1\n0\n1\n1"],["10 10\n6 6\n4 10\n2 5\n1 7\n3 4\n5 7\n4 10\n1 7\n1 3\n2 5\n8 8 5 1\n4 7 5 3\n5 9 4 4\n1 5 5 2\n6 2 10 2\n3 3 7 4\n1 10 1 2\n6 2 4 4\n9 2 1 4\n9 10 3 2","0\n17\n2\n0\n0\n46\n0\n12\n23\n1"],["10 10\n2 6\n6 9\n5 7\n3 9\n0 0\n0 0\n3 5\n5 5\n3 6\n1 10\n5 9 6 3\n10 8 6 4\n10 8 5 1\n8 6 5 4\n7 2 5 4\n6 1 5 3\n10 4 5 1\n5 5 6 0\n7 9 6 4\n4 9 6 2","0\n17\n1\n0\n0\n0\n1\n1\n4\n1"]],"created_at":"2026-03-03 11:09:25"}}