n370. 4. 蛇梯棋 - 高中生程式解題系統

內容

　　蛇梯棋是一款老少咸宜的桌遊，身為一位數學家，管它是淺顯還是易懂，我們必須要算點什麼。今天的任務是，給一張蛇梯棋的地圖，在忽略掉遇到蛇會回到前面的格子的情況下，請計算出有多少種移動方式能夠到達終點。

　　這是一張有 $N$ 個格子的矩形棋盤，將每一格依序編號為 $1 \sim N$ ，棋盤上包含多個梯子，一個梯子以起點與終點連接棋盤中的兩格 $i, j$ （ $1 < i < j \leq N$ ）， $i$ 為梯子起點， $j$ 為梯子終點，每一格最多只會有一個梯子的起點，但可能有多個梯子的終點。
　　遊戲一開始，玩家會在棋盤中的第 $1$ 格，玩家以每次擲骰子的點數 $x$ （ $1 \leq x \leq 6$ ）為前進步數，從 $i$ 移動到 $min (i + x, N)$ ，若 $i + x$ 包含了某個梯子的起點，就必須直接前往梯子的終點。注意，每次移動只會爬一次梯子，即便到達梯子的終點後該位置仍然有其它梯子的起點。遊戲將持續直到玩家到達最後一格 $N$ 就視為遊戲結束。
　　每一輪擲骰子的點數 $x$ 不同即為不同的走法，請計算能夠到達 $N$ 的方法數。

輸入說明

　　輸入的第一行包含兩個正整數 $N, K$ （ $1 \leq N \leq 4 \times 10^{5}, 0 \leq K \leq N - 2$ ），代表這張地圖共有 $N$ 格與 $K$ 個梯子。
　　接下來有 $K$ 行，每行有兩個整數 $i, j$ （ $1 < i < j \leq N$ ），代表一個梯子的起點與終點。

輸出說明

　　請輸出到達終點的步數，答案可能很大，請對 $998244353$ 取模後輸出。

範例輸入 #1

範例輸出 #1

範例輸入 #2

2 0

範例輸出 #2

測資資訊：

記憶體限制： 512 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 , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#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 , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

　　範例輸入 #1 與附圖相同。

本題共有 $3$ 個子題，每個子題有多筆測資。
第一子題：　 $N \leq 20$ ，全部解出可得 $15$ 分。
第二子題：　 $N \leq 2 \times 10^{5}$ ，全部解出可得 $35$ 分。
第三子題：　 $N \leq 4 \times 10^{5}$ ，全部解出可得 $50$ 分。

標籤:

出處:

112學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」