搭到終點 題解｜APCS 2024 年 10 月高級 第 4 題
前置知識
這題是「計數 DP ＋ 轉移是一段連續和」的經典，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：
- DP 的狀態與轉移：NTUCPC Guide〈狀態與轉移〉——計數題的 DP 存的是「方法數」，轉移用加法。
- 前綴和：NTUCPC Guide〈前綴和與差分〉——一段連續的和用兩個前綴和相減，\(O(1)\)。
- 排序與離散化：吳邦一《AP325》的 P-2-2 離散化——座標很大但「有用的座標」很少時，排序去重後改用「第幾個」當下標。
簡潔題意
你在位置 \(0\)，要搭公車到位置 \(m\)。第 \(i\) 班車從 \(l_i\) 開到 \(r_i\)：目前位置 \(x\) 只要滿足 \(l_i \le x < r_i\) 就能上車，上了就一定坐到 \(r_i\) 才能下。只能靠搭車往前。兩條搭乘序列只要某一次搭的公車編號不同就算不同（路線一樣也算不同）。求抵達 \(m\) 的搭乘序列數除以 \(p\) 的餘數（\(1 \le n \le 2 \times 10^5\)，\(1 \le m \le 10^9\)，\(1 \le p \le 10^9 + 9\)，\(0 \le l_i < r_i \le m\)）。
依正確通過的測試資料筆數給分，其中：
- 子題組 1（\(20\) 分）：\(n, m \le 100\)。
- 子題組 2（\(40\) 分）：\(m \le 10^5\)。
- 子題組 3（\(40\) 分）：無額外限制。
先拿下 20 分：每個位置都是一個狀態
搭完一班車，人一定停在它的終點；而且位置只會變大。所以照位置由小到大算：
\(dp[x]\) ＝ 抵達位置 \(x\) 的搭乘序列數，\(dp[0] = 1\)（什麼都還沒搭）。
站在位置 \(x\) 時，每一班「可以上」的車（\(l_i \le x < r_i\)）都把 \(dp[x]\) 種走法送到 \(r_i\)：\(dp[r_i] \mathrel{+}= dp[x]\)。因為 \(r_i > x\)，處理到 \(x\) 時 \(dp[x]\) 已經不會再變了。答案是 \(dp[m]\)，每一步都對 \(p\) 取餘數。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
long long p;
cin >> n >> m >> p;
vector<int> l(n), r(n);
for (int &v : l) cin >> v;
for (int &v : r) cin >> v;
vector<long long> dp(m + 1, 0); // dp[x]：抵達位置 x 的序列數
dp[0] = 1 % p; // p 可能是 1，連初始值都要取餘數
for (int x = 0; x <= m; x++)
for (int i = 0; i < n; i++)
if (l[i] <= x && x < r[i]) // 在 x 可以上第 i 班車
dp[r[i]] = (dp[r[i]] + dp[x]) % p;
cout << dp[m] << '\n';
return 0;
}
每個位置掃全部公車，\(O(nm) \le 10^4\)。範例 1 走一遍：\(dp[4] = 1\)、\(dp[6] = 1 + 2 = 3\)、\(dp[7] = dp[3] + dp[4] + dp[5] + dp[6] = 4\)、\(dp[9] = dp[5] + \cdots + dp[8] = 7\)（圖 1）。\(m\) 一大這份程式就太慢也開不下，但子題組 1 的 \(20\) 分穩穩到手。
從 20 分到 60 分：換成「每班車收一段連續和」
反過來看每一班車：從 \(l\) 到 \(r\) 這班車能接在任何抵達 \(l, l+1, \ldots, r-1\) 的序列後面，所以它貢獻給 \(dp[r]\) 的是
\[dp[l] + dp[l+1] + \cdots + dp[r-1]\]——一段連續和，用前綴和 \(pre[t] = dp[0] + \cdots + dp[t-1]\) 就是 \(pre[r] - pre[l]\)。問題只剩「算到這班車時，\(dp[l..r-1]\) 都確定了嗎」：把公車依終點 \(r\) 由小到大排序再處理，輪到終點 \(r\) 的車時，所有終點小於 \(r\) 的車都處理完了，位置 \(< r\) 的 \(dp\) 都已經是最終值；前綴和跟著一路往右補到 \(r\) 就好。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
long long p;
cin >> n >> m >> p;
vector<int> l(n), r(n);
for (int &v : l) cin >> v;
for (int &v : r) cin >> v;
vector<int> order(n); // 公車編號依終點由小到大排
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return r[a] < r[b]; });
vector<long long> dp(m + 1, 0), pre(m + 2, 0); // pre[t] = dp[0] + ... + dp[t-1]
dp[0] = 1 % p;
int done = 0; // pre 已經算到 done（dp[0..done-1] 都確定了）
for (int i : order) {
while (done < r[i]) { // 把前綴和補到終點前一格
pre[done + 1] = (pre[done] + dp[done]) % p;
done++;
}
dp[r[i]] = (dp[r[i]] + pre[r[i]] - pre[l[i]] + p) % p; // 抵達 [l, r) 的序列都能接這班車
}
cout << dp[m] << '\n';
return 0;
}
排序 \(O(n \log n)\)，前綴和與每班車各 \(O(1)\)，總共 \(O(n \log n + m)\)。相減後可能是負的，所以 + p 再取餘數；\(dp\) 和 \(pre\) 都小於 \(p\)，兩個相加不會超過 long long。\(m\) 到 \(10^9\) 時陣列開不出來——這是子題組 3 要解決的事。
從 60 分到 100 分：只有公車端點的位置才重要
\(m\) 到 \(10^9\) 但公車只有 \(2 \times 10^5\) 班。\(dp[x]\) 只有在 \(x\) 是某班車的終點（或 \(0\)）時才可能不是 \(0\)，前綴和也只在 \(l_i\)、\(r_i\) 這些位置被查到——所以把 \(0\)、\(m\)、所有 \(l_i\)、\(r_i\) 收集起來排序去重，用「它是第幾個座標」當下標，上面的程式一行都不用改思路，只是查表前先用 lower_bound 把位置換成編號。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
long long p;
cin >> n >> m >> p;
vector<int> l(n), r(n);
for (int &v : l) cin >> v;
for (int &v : r) cin >> v;
vector<int> xs = {0, m}; // 所有會用到的位置
for (int i = 0; i < n; i++) {
xs.push_back(l[i]);
xs.push_back(r[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end()); // 去重：xs[t] 是第 t 個位置
int c = xs.size();
auto id = [&](int v) { return int(lower_bound(xs.begin(), xs.end(), v) - xs.begin()); };
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return r[a] < r[b]; });
vector<long long> dp(c, 0), pre(c + 1, 0); // 下標改成「第幾個位置」
dp[0] = 1 % p; // xs[0] 一定是 0
int done = 0;
for (int i : order) {
int a = id(l[i]), b = id(r[i]);
while (done < b) {
pre[done + 1] = (pre[done] + dp[done]) % p;
done++;
}
dp[b] = (dp[b] + pre[b] - pre[a] + p) % p;
}
cout << dp[c - 1] << '\n'; // xs[c-1] 一定是 m
return 0;
}
座標最多 \(2n + 2\) 個，排序、去重、每班車一次二分搜，總共 \(O(n \log n)\)；\(n = 2 \times 10^5\) 本站實測不到 \(0.2\) 秒。
測過再交：範例裡沒有「剛好在端點」的局面
兩個範例的公車都是從 \(0\) 或中途上車、終點各不相同。沒蓋到的：剛好在某班車的起點上車、到了終點不能再上同一班、同路線的兩班車、\(p = 1\)、到不了、\(m\) 很大。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
1 1 5 ／ 0 ／ 1 |
1 |
最小的輸入 |
2 5 100 ／ 0 3 ／ 3 5 |
1 |
第一班的終點 \(3\) 剛好是第二班的起點：\(l \le x\) 的等號要放行 |
2 3 100 ／ 0 1 ／ 3 3 |
1 |
到了位置 \(3\) 不能再上終點是 \(3\) 的第二班：\(x < r\) 不含等號 |
2 5 100 ／ 0 0 ／ 5 5 |
2 |
兩班車路線完全相同，編號不同就是兩種序列 |
1 5 1 ／ 0 ／ 5 |
0 |
\(p = 1\)：任何數除以 \(1\) 餘 \(0\)，連 \(dp[0]\) 都要取餘數 |
2 6 100 ／ 0 4 ／ 3 6 |
0 |
第一班到 \(3\)、第二班 \(4\) 才能上：到不了 |
1 1000000000 7 ／ 0 ／ 1000000000 |
1 |
\(m = 10^9\)：陣列開不下，一定要離散化 |
七筆都親眼看過正確，這題就穩了。
常犯錯誤
- 到了終點 \(r\) 還讓人上同一班車（寫成 \(x \le r\)）：自測表第 3 列印
2；本站 \(22\) 筆測資掛 \(10\) 筆。 - 剛好在起點 \(l\) 不讓上車（寫成 \(l < x\)）：從 \(0\) 出發的第一班車就上不了，範例 1、2 都印
0；本站掛 \(12\) 筆。 - 公車沒依終點排序就一班一班累加前綴和：兩個範例都剛好對，本站卻掛 \(7\) 筆——後面才讀到的車如果終點比較小，它貢獻的 \(dp\) 值在前綴和裡已經算不到了。
- 最後才取餘數：序列數會像 \(2^{70}\) 那樣爆掉
long long；本站掛 \(3\) 筆。 - 直接開 \(m\) 大小的陣列：\(m = 10^9\) 開不出來，子題組 3 全掛；\(O(nm)\) 的做法在 \(m = 10^5\) 也超過時限，本站掛 \(14\) 筆。