No.802 だいたい等差数列
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 104
作問者 :
tempura_pp
/ テスター :
heno239
タグ : / 解いたユーザー数 104
作問者 :
tempura_pp
/ テスター :
heno239
問題文最終更新日: 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$
入力
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。