a330. TOI 2023/05 潛力組：載運貨物

題目描述

N 箱貨物由左至右排成一列，編號 1 至 N，第 i 箱重 W_i 公斤。裝車時只能從尚未搬走的最左端取貨，不能跳過前面的貨物。每一趟貨車的載重都必須介於 L 與 U 公斤之間，包含兩個端點。

請計算依上述規則把所有貨物分趟運完，共有多少種合法的分裝方法。不同的分趟界線視為不同方法。答案可能很大，請對 10^9+7 取餘數。

輸入格式

第一行為三個正整數 N、L、U，1 ≤ N ≤ 2×10^5，1 ≤ L ≤ U ≤ 10^9。

第二行有 N 個正整數 W_1 至 W_N，1 ≤ W_i ≤ 10^3。相鄰數字以空白分隔。

原題分組限制：30 分：N ≤ 15。40 分：N ≤ 2×10^3。30 分：無額外限制。

輸出格式

輸出一個非負整數，表示所有合法載運方法數除以 10^9+7 的餘數。

範例 1

輸入：

5 4 8
3 5 4 3 4

輸出：

2

範例 2

輸入：

5 4 7
3 5 4 3 4

輸出：

0

範例 3

輸入：

7 3 11
5 2 4 6 1 7 2

輸出：

8

範例 4

輸入：

8 2 7
4 7 1 3 5 6 4 3

輸出：

2

來源

TOI 2023 年 5 月歷屆題〈載運貨物〉，依官方 PDF 重新整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202305/Cargo.pdf

標籤：TOI 歷屆