Phân đoạn


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Cho dãy số $a_1,a_2,...,a_N$ và hai số $L$, $R$. Một cách phân đoạn dãy $a$ là cách chia dãy $a$ thành một hoặc một số đoạn, mỗi đoạn là một chuỗi các phần tử liên tục trong mảng $a$.

Đếm số cách phân đoạn dãy $a$ sao cho tổng của mỗi đoạn con nằm trong đoạn $[l, r]$.

Dữ liệu

  • Dòng đầu tiên chứa ba số nguyên $N,L,R \ (1\le N\le 10^5; 1\le L\le R\le 10^{12})$;
  • Dòng tiếp theo chứa $N$ số nguyên $a_i \ (1 \le a_i \le R)$.

Kết quả

  • Kết quả bài toán sau khi chia lấy dư cho $10^9+7$.

Chấm điểm

30; $N\le 20$. 30; $N\le 10^3$. 40; Không có giới hạn gì thêm.

Ví dụ

Ví dụ 1

input

5 3 12
3 5 1 2 6

output

8

Giải thích

Các cách phân đoạn:

  • (3)(5)(1 2 6)
  • (3)(5 1)(2 6)
  • (3)(5 1 2)(6)
  • (3 5)(1 2)(6)
  • (3 5)(1 2 6)
  • (3 5 1)(2 6)
  • (3 5 1 2)(6)
  • (3)(5)(1 2)(6)

Comments

There are no comments at the moment.