TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6618
  • 問題
  • P6618跳跃游戏
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,512m
    問題説明

    何老板在玩一款跳跃小游戏,游戏虽然简单,何老板仍旧乐此不疲。

    游戏地图是n+1块石头排成一条直线,石头编号0到n,相邻石头间间距为1米。

    0时刻,何老板操控的游戏角色马跃奥位于0号石头上,游戏目标是跳跃到第n号石头上去。

    马跃奥的跳跃能力很强,他跳一次至少会跨越d米,即从i号石头起跳,最近的落点是i+d号石头。跳一次耗时1秒。

    游戏中有m次砖块坠落,每一次坠落可以描述成两个整数Ti和Pi,表示在Ti秒钟,有一块砖会从天而降落在第Pi号石头上,如果此时马跃奥恰好落在第Pi号石头上,他就会被砸身亡。

    游戏规定,不可以在石头上停滞不前,着陆以后必须立即起跳。

    何老板想知道,要成功到达n号石头,有多少种不同的方案。

    mod 998244353再输出。

    入力形式

    第一行三个整数n,d,m
    接下来m行,每行一个整数,表示一次落砖发生的时间和地点

    出力形式

    一个整数,表示计算结果

    サンプル入力

    5 2 1
    1 2

    サンプル出力

    2

    方案1:0——3——5  
    方案2:0——5

    ヒント

    $1<=d<=n<=10^7$
    $1<=Ti,Pi<n$
    $1<=m<=3000$


    ソース  niuke2019t8Just Jump