問題一覧 > 通常問題

No.802 だいたい等差数列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 100
作問者 : tempura_pptempura_pp / テスター : heno239heno239
26 ProblemId : 2778 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-03-14 18:50:58

問題文

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

  • $1 \le A_1 \le A_2 \le \ ...\ \le A_N \le M$
  • $1\le i \le N-1$なるすべての整数$i$に対して、$D_1 \le A_{i+1}-A_i \le D_2$
ただし、数列$A'$と$A''$が異なるとは、ある$i$が存在して$A'_i\ne A''_i$であることをいいます。

入力

$N\ M\ D_1\ D_2$

  • $2\le N \le 3×10^5$
  • $1\le M\le 10^6$
  • $0\le D_1\le D_2\le M$
  • 入力はすべて整数

出力

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

サンプル

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

条件をみたす数列は以下の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
出力
1

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

サンプル4
入力
3141 592653 58 97
出力
200759484

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