j06625. 冲刺·合法划分 · 林老师的题库

题目描述

仓库里排着 $N$ 件货物，从左到右第 $i$ 件的重量为 $a_{i}$ 。现在要把这排货物按顺序装上 $K$ 辆卡车：在相邻货物之间选 $K - 1$ 个切割位置，把整排恰好分成 $K$ 段连续非空的子段，第 $j$ 辆卡车装走第 $j$ 段。

每辆卡车的载重上限都是 $S$ ，因此每一段的重量之和都不能超过 $S$ 。

请求出满足条件的划分方案数，答案对 $1 0^{9} + 7$ 取模。

第一行三个整数 $N, K, S$ ，用空格分隔。

第二行 $N$ 个正整数 $a_{1}, a_{2}, \dots, a_{N}$ ，用空格分隔。

输出一个整数，表示合法划分方案数对 $1 0^{9} + 7$ 取模后的结果。

输入

4 2 4
1 2 1 2

输出

【样例解释】

样例 1：要分成 $2$ 段且每段和不超过 $4$ 。 $[1, 2]$ 与 $[1, 2]$ （和 $3, 3$ ）合法； $[1, 2, 1]$ 与 $[2]$ （和 $4, 2$ ）合法； $[1]$ 与 $[2, 1, 2]$ （第二段和 $5 > 4$ ）不合法。共 $2$ 种。
样例 2：只有 $[5]$ 与 $[5, 5]$ （和 $5, 10$ ）或 $[5, 5]$ 与 $[5]$ （和 $10, 5$ ）两种切法，都有一段和为 $10 > 8$ ，故方案数为 $0$ 。

【数据规模与约定】

对于全部数据，满足 $1 \leq K \leq N \leq 6000$ ， $1 \leq S \leq 1 0^{9}$ ， $1 \leq a_{i} \leq S$ 。

共 20 个测试点，每个测试点 5 分，合计 100 分。