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 \le n \le 2 \times 10^5, 1 \le m \le 10^9, 1 \le p \le 10^9 + 9)$ 代表有 $n$ 個公車路線，終點在 $m$ 以及答案要 mod 的整數 $p$。
接下來一行有 $n$ 個數字，代表每一個公車路線的起始位置。
最後一行有 $n$ 個數字，代表每一個公車路線的終點位置。

(20%): $1 \le n, m \le 100$
(40%): $1 \le m \le 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@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
43638	aadreamoon@g ... (AA 競程)	o714	此題解有分別介紹拿 20、60、100 分的作法，循序漸進唷！	90	2024-10-22 02:05
43635	ptyc4076@gma ... (Bernie)	o714	解	76	2024-10-21 22:02
43514	ericshen1955 ... (暴力又被TLE)	o714	很詳細ㄉ題解 \(・∀・)/	202	2024-10-21 11:40