問題一覧 > 通常問題

No.1191 数え上げを愛したい（数列編）

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : sanada_atcoder / テスター : Rho
18 ProblemId : 4390 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-17 22:30:27

問題文

次の条件を満たす長さ N の数列 S として考えられるものの通り数を 998244353 で割った余りを求めてください。

  • 数列の各要素は 1 以上 M 以下の整数である。
  • 1≤i<j≤N を満たす任意の i,j において、 A≤|Si−Sj|≤B を満たす。

    • 入力

    N M A B

    入力で与えられる数は全て整数である。
    2≤N≤105
    2≤M≤3×105
    1≤A≤B≤M−1

    出力

    998244353 で割った余りを求めてください。最後に改行してください。

    サンプル

    サンプル1
    入力
    2 2 1 1
    出力
    2

    {1,2} , {2,1} の2通りあります。

    サンプル2
    入力
    3 5 1 1
    出力
    0

    条件を満たす数列は存在しません。

    サンプル3
    入力
    4 19 3 15
    出力
    11088

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。