o714. 4. 搭到終點 - 高中生程式解題系統

內容

有一個數線從 $0$ 到 $m$ ，你一開始在位置 $0$ 上，想要搭公車到位置 $m$ 處。
有 $n$ 台公車路線可以選擇，每一公車路線都有其行駛的起點和終點。

例如你想要到位置 $m = 9$ ，且有 $n = 5$ 條公車路線如下

公車路線編號	1	2	3	4	5
路線起終點	[0, 4]	[4, 6]	[0, 6]	[3, 7]	[5, 9]

你可以任意地決定公車何時出發，並且在公車的路線範圍內都可以上車，但一定會搭到該路線的終點才下車，且不可在同一位置同時上下車。

你想知道總共有幾種搭車方式可以到位置 $m$ 。如上述例子總共有 $7$ 種搭車方式，分別如下列：
(1) 1 -> 2 -> 4 -> 5 (先搭乘路線1 到位置 $4$ ，再搭乘路線2 到位置 $6$ ，接著搭乘路線4 到位置 $7$ ，最後搭乘路線5 到位置 $9$ )
(2) 1 -> 2 -> 5
(3) 1 -> 3 -> 4 -> 5
(4) 1 -> 3 -> 5
(5) 1 -> 4 -> 5
(6) 3 -> 4 -> 5
(7) 3 -> 5

由於搭乘方式數量可能很大，請輸出搭乘方式數量 mod $p$ 的結果。

輸入說明

第一行有三個正整數 $n, m, p (1 \leq n \leq 2 \times 10^{5}, 1 \leq m \leq 10^{9}, 1 \leq p \leq 10^{9} + 9)$ 代表有 $n$ 個公車路線，終點在 $m$ 以及答案要 mod 的整數 $p$ 。
接下來一行有 $n$ 個數字，代表每一個公車路線的起始位置。
最後一行有 $n$ 個數字，代表每一個公車路線的終點位置。

(20%): $1 \leq n, m \leq 100$
(40%): $1 \leq m \leq 10^{5}$
(40%): 無限制

輸出說明

輸出共有幾種公車搭乘方式，由於答案數字可能很大，請輸出答案 mod $p$ 的結果。

範例輸入 #1

5 9 11
0 4 0 3 5
4 6 6 7 9

範例輸出 #1

範例輸入 #2

6 8 4
0 1 2 3 5 6
3 6 6 6 8 8

範例輸出 #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <10M
公開測資點#5 (5%): 1.0s , <10M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

感謝 fantastic1211 提供題目資訊

標籤:

出處:

2024年10月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
45220	john1100729@ ... (靖諺)	o714	C++ 詳解(含第1~4題)	91	2025-01-26 22:07
44475	leeguanhan09 ... (李冠翰)	o714	Python 實作題1~4題詳解	167	2024-12-08 23:12
43763	samlin961112 ... (林哲甫)	o714	解題想法&C++答案&註解	1031	2024-10-28 17:18
43638	aadreamoon@g ... (AA 競程)	o714	此題解有分別介紹拿 20、60、100 分的作法，循序漸進唷！	754	2024-10-22 02:05
43635	ptyc4076@gma ... (Bernie)	o714		205	2024-10-21 22:02