No.802 だいたい等差数列

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.802 だいたい等差数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 104
作問者 :

tempura_pp / テスター :

heno239

26 ProblemId : 2778 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2019-03-14 18:50:58

問題文

長さ $N$ の整数列 $A_{1}, A_{2}, . . ., A_{N}$ であって、以下の条件をすべてみたすものの個数を $10^{9} + 7$ で割った余りを求めてください。

$1 \leq A_{1} \leq A_{2} \leq . . . \leq A_{N} \leq M$
$1 \leq i \leq N - 1$ なるすべての整数 $i$ に対して、 $D_{1} \leq A_{i + 1} - A_{i} \leq D_{2}$

ただし、数列

A^{'}

と

A^{″}

が異なるとは、ある

i

が存在して

A_{i}^{'} \neq A_{i}^{″}

であることをいいます。

入力

 $N M D_{1} D_{2}$

$2 \leq N \leq 3 \times 10^{5}$
$1 \leq M \leq 10^{6}$
$0 \leq D_{1} \leq D_{2} \leq M$
入力はすべて整数

出力

条件をみたす整数列の個数を $10^{9} + 7$ で割った余りを1行に出力してください。

サンプル

サンプル1

入力

3 5 1 2

出力

条件をみたす数列は以下の8つです。
$(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 3, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)$

サンプル2

入力

3 5 2 2

出力

サンプル3

入力

5 2 1 1

出力

サンプル4

入力

3141 592653 58 97

出力

200759484

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

yukicoder

No.802 だいたい等差数列

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力