蛇梯棋是一款老少咸宜的桌遊，身為一位數學家，管它是淺顯還是易懂，我們必須要算點什麼。今天的任務是，給一張蛇梯棋的地圖，在忽略掉遇到蛇會回到前面的格子的情況下，請計算出有多少種移動方式能夠到達終點。
這是一張有 $N$ 個格子的矩形棋盤，將每一格依序編號為 $1\sim N$，棋盤上包含多個梯子，一個梯子以起點與終點連接棋盤中的兩格 $i, j$（$1<i<j\le N$），$i$ 為梯子起點，$j$ 為梯子終點，每一格最多只會有一個梯子的起點，但可能有多個梯子的終點。
遊戲一開始，玩家會在棋盤中的第 $1$ 格，玩家以每次擲骰子的點數 $x$（$1\le x\le 6$）為前進步數，從 $i$ 移動到 $\text{min}(i+x, N)$，若 $i+x$ 包含了某個梯子的起點，就必須直接前往梯子的終點。注意，每次移動只會爬一次梯子，即便到達梯子的終點後該位置仍然有其它梯子的起點。遊戲將持續直到玩家到達最後一格 $N$ 就視為遊戲結束。
每一輪擲骰子的點數 $x$ 不同即為不同的走法，請計算能夠到達 $N$ 的方法數。
輸入的第一行包含兩個正整數 $N, K$（$1\le N\le 4\times 10^5, 0\le K\le N-2$），代表這張地圖共有 $N$ 格與 $K$ 個梯子。
接下來有 $K$ 行，每行有兩個整數 $i, j$（$1<i<j\le N$），代表一個梯子的起點與終點。
請輸出到達終點的步數，答案可能很大，請對 $998244353$ 取模後輸出。
25 4 2 23 11 21 4 8 14 25
2098571
2 0
6
公開 測資點#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\le20$，全部解出可得 $15$ 分。
第二子題： $N\le 2\times 10^5$，全部解出可得 $35$ 分。
第三子題： $N\le 4\times 10^5$，全部解出可得 $50$ 分。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||