問題一覧 > 通常問題

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

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

問題文

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

  • 数列の各要素は $1$ 以上 $M$ 以下の整数である。
  • $1 \le i < j \le N$ を満たす任意の $i,j$ において、 $A \le |S_i-S_j| \le B$ を満たす。

    • 入力

    $N\ M\ A\ B$

    入力で与えられる数は全て整数である。
    $2 \le N \le 10^5$
    $2 \le M \le 3×10^5$
    $1 \le A \le B \le 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もしくは右上の雲マークをクリックしてアカウントを作成してください。