題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。
題目簡述
有 N N N 1 1 1 N N N M M M [ L i , R i ] [L_i, R_i] [ L i , R i ] L i L_i L i R i R_i R i A A A B B B 1 1 1 N N N
約束條件
2 ≤ N ≤ 1 0 12 2 \leq N \leq 10^{12} 2 ≤ N ≤ 1 0 1 2 0 ≤ M ≤ 2 × 1 0 4 0 \leq M \leq 2 \times 10^4 0 ≤ M ≤ 2 × 1 0 4 1 ≤ A ≤ B ≤ 20 1 \leq A \leq B \leq 20 1 ≤ A ≤ B ≤ 2 0 1 < L i ≤ R i < N 1 < L_i \leq R_i < N 1 < L i ≤ R i < N R i < L i + 1 R_i < L_{i+1} R i < L i + 1 所有輸入皆為整數
如果只看能不能抵達，其實可以用布林 DP；但為了更自然地推導矩陣形式，可以先把它想成「方案數」問題。
令 f i f_i f i i i i i i i good ，則可以從距離 A A A B B B
f i = ∑ j = A B f i − j f_i = \sum_{j=A}^{B} f_{i-j}
f i = j = A ∑ B f i − j
若位置 i i i bad ，則不能落腳，因此不存在任何轉移來源，也就是 f i = 0 f_i = 0 f i = 0
每次轉移只會用到最近 B B B B ≤ 20 B \leq 20 B ≤ 2 0 B B B
以下以 A = 3 , B = 5 A = 3, B = 5 A = 3 , B = 5 good ，新的最上方狀態會由前方距離 3 3 3 5 5 5
[ f i f i − 1 f i − 2 f i − 3 f i − 4 ] = [ 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 ] [ f i − 1 f i − 2 f i − 3 f i − 4 f i − 5 ] \begin{bmatrix}
f_i \\
f_{i-1} \\
f_{i-2} \\
f_{i-3} \\
f_{i-4}
\end{bmatrix}
=
\begin{bmatrix}
0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
f_{i-1} \\
f_{i-2} \\
f_{i-3} \\
f_{i-4} \\
f_{i-5}
\end{bmatrix}
⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ f i f i − 1 f i − 2 f i − 3 f i − 4 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ f i − 1 f i − 2 f i − 3 f i − 4 f i − 5 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
若目前位置是 bad ，新的最上方狀態必定是 0 0 0
[ f i f i − 1 f i − 2 f i − 3 f i − 4 ] = [ 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 ] [ f i − 1 f i − 2 f i − 3 f i − 4 f i − 5 ] \begin{bmatrix}
f_i \\
f_{i-1} \\
f_{i-2} \\
f_{i-3} \\
f_{i-4}
\end{bmatrix}
=
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
f_{i-1} \\
f_{i-2} \\
f_{i-3} \\
f_{i-4} \\
f_{i-5}
\end{bmatrix}
⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ f i f i − 1 f i − 2 f i − 3 f i − 4 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ f i − 1 f i − 2 f i − 3 f i − 4 f i − 5 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
初始狀態是 f 1 = 1 f_1 = 1 f 1 = 1 f 0 = f − 1 = ⋯ = f − B + 2 = 0 f_0 = f_{-1} = \cdots = f_{-B+2} = 0 f 0 = f − 1 = ⋯ = f − B + 2 = 0
x = [ f 1 f 0 f − 1 f − 2 f − 3 ] = [ 1 0 0 0 0 ] \mathbf{x} =
\begin{bmatrix}
f_1 \\
f_0 \\
f_{-1} \\
f_{-2} \\
f_{-3}
\end{bmatrix}
=
\begin{bmatrix}
1 \\
0 \\
0 \\
0 \\
0
\end{bmatrix}
x = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ f 1 f 0 f − 1 f − 2 f − 3 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 0 0 0 0 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
題目給出的壞區間互不重疊且已排序，因此整條路可以被切成若干段 good 與 bad 。每次從某個已處理位置推進到另一個位置時，若中間這段性質相同，就等同於重複套用同一個轉移矩陣。
若目前已處理到位置 s t st s t e d ed e d e d − s t ed - st e d − s t ( s t , e d ] (st, ed] ( s t , e d ] ( 1 , L 1 − 1 ] (1, L_1 - 1] ( 1 , L 1 − 1 ] ( L 1 − 1 , R 1 ] (L_1 - 1, R_1] ( L 1 − 1 , R 1 ] ( R M , N ] (R_M, N] ( R M , N ]
利用矩陣快速冪，可以把同一種矩陣的 k k k 2 j 2^j 2 j
但如果對每一段都直接做一次矩陣快速冪，會超時。原因是每段都會重新計算 M 2 j M^{2^j} M 2 j B × B B \times B B × B O ( B 3 ) \mathcal{O}(B^3) O ( B 3 )
O ( M B 3 log N ) \mathcal{O}(M B^3 \log N)
O ( M B 3 log N )
根據本題資料範圍，粗略估算為：
2 × 1 0 4 × 2 0 3 × log 2 1 0 12 ≈ 6.4 × 1 0 9 2 \times 10^4 \times 20^3 \times \log_2 10^{12}
\approx 6.4 \times 10^9
2 × 1 0 4 × 2 0 3 × log 2 1 0 1 2 ≈ 6 . 4 × 1 0 9
這個量級明顯無法通過。
本題只會出現兩種轉移矩陣：好格矩陣與壞格矩陣。因此可以先預處理兩者的 2 0 , 2 1 , 2 2 , … 2^0, 2^1, 2^2, \ldots 2 0 , 2 1 , 2 2 , …
預處理只需要對兩種矩陣各做 O ( log N ) \mathcal{O}(\log N) O ( log N ) B × B B \times B B × B
O ( B 3 log N ) \mathcal{O}(B^3 \log N)
O ( B 3 log N )
實際上我們最後只需要目前的狀態向量。若先把所有矩陣冪乘成完整矩陣，再乘上狀態向量，會做很多次 B × B B \times B B × B B × 1 B \times 1 B × 1 O ( B 2 ) \mathcal{O}(B^2) O ( B 2 )
在經過兩種優化後，這樣每段轉移就能降到 O ( B 2 log N ) \mathcal{O}(B^2 \log N) O ( B 2 log N )
若只做預處理，但每段仍先把需要的矩陣冪互相乘成完整轉移矩陣，單段仍要做 O ( log N ) \mathcal{O}(\log N) O ( log N ) B × B B \times B B × B O ( M B 3 log N ) \mathcal{O}(M B^3 \log N) O ( M B 3 log N ) O ( B 2 log N ) \mathcal{O}(B^2 \log N) O ( B 2 log N )
前面的推導用方案數比較直觀，但本題只需要判斷是否存在一條路徑。若真的計算方案數，數字會非常大；即使取模，也可能出現「實際有方案，但取模後剛好是 0 0 0
所以程式把矩陣乘法中的「加法」改成或運算，把「乘法」改成與運算。如此一來，狀態值只表示可不可達：只要存在任一個合法來源，新位置就是可達。
時間複雜度：O ( B 3 log N + M B 2 log N ) \mathcal{O}(B^3 \log N + M B^2 \log N) O ( B 3 log N + M B 2 log N )
預處理好格矩陣與壞格矩陣的二次冪：兩種矩陣各做 O ( log N ) \mathcal{O}(\log N) O ( log N ) B × B B \times B B × B O ( B 3 log N ) \mathcal{O}(B^3 \log N) O ( B 3 log N )
區間轉移：壞區間會切出前方好格與自身壞格，最後還有一段尾端好格，段數是 O ( M ) \mathcal{O}(M) O ( M )
每段長度拆成二進位後，最多取 O ( log N ) \mathcal{O}(\log N) O ( log N ) B × B B \times B B × B B × 1 B \times 1 B × 1 O ( B 2 ) \mathcal{O}(B^2) O ( B 2 ) O ( B 2 log N ) \mathcal{O}(B^2 \log N) O ( B 2 log N )
合併後為 O ( B 3 log N + M B 2 log N ) \mathcal{O}(B^3 \log N + M B^2 \log N) O ( B 3 log N + M B 2 log N )
空間複雜度：O ( B 2 log N ) \mathcal{O}(B^2 \log N) O ( B 2 log N )
需要保存兩種轉移矩陣的二次冪，每個矩陣大小為 B 2 B^2 B 2 O ( log N ) \mathcal{O}(\log N) O ( log N )
目前狀態向量只需要 O ( B ) \mathcal{O}(B) O ( B )
除此之外，還能利用「只求可行性」這個性質，把矩陣的每一橫列壓成一個整數。
矩陣相乘時，若某一橫列的第 k k k 1 1 1 k k k
一般布林矩陣乘法需要枚舉三個維度；壓成整數後，橫列的合併由位元運算完成，因此矩陣相乘可以壓到 O ( B 2 ) \mathcal{O}(B^2) O ( B 2 )
在這個版本中，快速冪會先累積完整轉移矩陣，最後再乘上目前狀態向量。因為矩陣乘法本身已被位元壓縮優化，這樣寫仍然足夠快，也更接近一般快速冪的形式。
也就是說，第一份程式是避免在每段做 B × B B \times B B × B B × B B \times B B × B O ( B 2 log N ) \mathcal{O}(B^2 \log N) O ( B 2 log N )
位元壓縮版本中，矩陣與向量共用同一套表示方式。向量雖然只有一直行，但仍可視為每橫列只有最低位可能為 1 1 1
時間複雜度：O ( M B 2 log N + B 2 log N ) \mathcal{O}(M B^2 \log N + B^2 \log N) O ( M B 2 log N + B 2 log N )
位元壓縮後，一次 B × B B \times B B × B O ( B 2 ) \mathcal{O}(B^2) O ( B 2 )
預處理好格矩陣與壞格矩陣的二次冪需要 O ( B 2 log N ) \mathcal{O}(B^2 \log N) O ( B 2 log N )
每段快速冪最多做 O ( log N ) \mathcal{O}(\log N) O ( log N ) O ( B 2 log N ) \mathcal{O}(B^2 \log N) O ( B 2 log N )
總段數為 O ( M ) \mathcal{O}(M) O ( M ) O ( M B 2 log N + B 2 log N ) \mathcal{O}(M B^2 \log N + B^2 \log N) O ( M B 2 log N + B 2 log N )
空間複雜度：O ( B log N ) \mathcal{O}(B \log N) O ( B log N )
每個矩陣只需保存 B B B B B B
兩種矩陣各保存 O ( log N ) \mathcal{O}(\log N) O ( log N ) O ( B log N ) \mathcal{O}(B \log N) O ( B log N )
狀態向量需要 O ( B ) \mathcal{O}(B) O ( B )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 N, M, A, B = map (int , input ().split()) intervals = [tuple (map (int , input ().split())) for _ in range (M)] class Matrix : def __init__ (self, mat ): self.mat = mat def __mul__ (self, other ): p, q, r = len (self.mat), len (other.mat), len (other.mat[0 ]) res = [[0 ] * r for _ in range (p)] for k in range (q): for i in range (p): for j in range (r): res[i][j] |= self.mat[i][k] & other.mat[k][j] return Matrix(res) def __getitem__ (self, key ): i, j = key return self.mat[i][j] def __setitem__ (self, key, value ): i, j = key self.mat[i][j] = value MG = Matrix([[0 ] * B for _ in range (B)]) for i in range (A - 1 , B): MG[0 , i] = 1 for i in range (1 , B): MG[i, i - 1 ] = 1 MB = Matrix([[0 ] * B for _ in range (B)]) for i in range (1 , B): MB[i, i - 1 ] = 1 pow_MG, pow_MB = [0 ] * 41 , [0 ] * 41 pow_MG[0 ], pow_MB[0 ] = MG, MB for i in range (1 , 41 ): pow_MG[i] = pow_MG[i - 1 ] * pow_MG[i - 1 ] pow_MB[i] = pow_MB[i - 1 ] * pow_MB[i - 1 ] def pow (x, k, pow_mat ): """ 根據矩陣快速冪，可以把 MB^k 表示成 MB^(2^i) 的乘積。 因此在預先處理完 MB^(2^i) 的矩陣後，需要計算若干個 (B x B) 的矩陣相乘後再乘以一個 (B x 1) 的矩陣。 但注意這裡有個小技巧： 兩個 (B x B) 的矩陣相乘需要 O(B^3) 的時間； 而 (B x B) 的矩陣乘以 (B x 1) 的矩陣只需要 O(B^2) 的時間。 因此我們應該由後往前計算，這樣可以減少計算的次數。 如此便可以在 O(B^2 log k) 的時間內計算出 MB^k * x 。 """ res = x for i in range (41 ): if k & (1 << i): res = pow_mat[i] * res return res cur = 1 m = [[0 ] for _ in range (B)] m[0 ] = [1 ] x = Matrix(m) for (L, R) in intervals: x = pow (x, L - 1 - cur, pow_MG) x = pow (x, R - L + 1 , pow_MB) cur = R x = pow (x, N - cur, pow_MG) print ("Yes" if x[0 , 0 ] else "No" )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 N, M, A, B = map (int , input ().split()) intervals = [tuple (map (int , input ().split())) for _ in range (M)] class Matrix : def __init__ (self, r, c, mat=None ): self.r = r self.c = c self.mat = mat or [0 ] * r def __mul__ (self, other ): res = [0 ] * len (self.mat) for i in range (len (self.mat)): row = self.mat[i] for k in range (len (other.mat)): if row & (1 << k): res[i] |= other.mat[k] return Matrix(self.r, other.c, res) def __getitem__ (self, key ): i, j = key return (self.mat[i] >> j) & 1 def __setitem__ (self, key, value ): i, j = key if value: self.mat[i] |= (1 << j) else : self.mat[i] &= ~(1 << j) MG = Matrix(B, B) for i in range (A - 1 , B): MG[0 , i] = 1 for i in range (1 , B): MG[i, i - 1 ] = 1 MB = Matrix(B, B) for i in range (1 , B): MB[i, i - 1 ] = 1 pow_MG, pow_MB = [0 ] * 41 , [0 ] * 41 pow_MG[0 ], pow_MB[0 ] = MG, MB for i in range (1 , 41 ): pow_MG[i] = pow_MG[i - 1 ] * pow_MG[i - 1 ] pow_MB[i] = pow_MB[i - 1 ] * pow_MB[i - 1 ] identity = Matrix(B, B) for i in range (B): identity[i, i] = 1 def pow (x, k, pow_mat ): """ 根據矩陣快速冪，可以把 MB^k 表示成 MB^(2^i) 的乘積。 因此在預先處理完 MB^(2^i) 的矩陣後，需要計算若干個 (B x B) 的矩陣相乘後再乘以一個 (B x 1) 的矩陣。 但注意這裡有個小技巧： 兩個 (B x B) 的矩陣相乘需要 O(B^3) 的時間； 而 (B x B) 的矩陣乘以 (B x 1) 的矩陣只需要 O(B^2) 的時間。 因此我們應該由後往前計算，這樣可以減少計算的次數。 如此便可以在 O(B^2 log k) 的時間內計算出 MB^k * x 。 不過如果用狀態壓縮 + 位運算，則計算兩個 (B x B) 的矩陣相乘只需要 O(B^2) 的時間。 """ res = identity for i in range (41 ): if k & (1 << i): res = pow_mat[i] * res return res * x cur = 1 m = [0 ] * B m[0 ] = 1 x = Matrix(B, 1 , m) for (L, R) in intervals: x = pow (x, L - 1 - cur, pow_MG) x = pow (x, R - L + 1 , pow_MB) cur = R x = pow (x, N - cur, pow_MG) print ("Yes" if x[0 , 0 ] else "No" )
