Sequence Partition

Sequence Partition

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个正整数序列\(\{a_i\}, i=1,2 \cdots N\),要求将其 划分 成恰好\(K\)个 非空 子段,每个子段内的元素之和\(\le S\),求划分方案的总数。
“划分”指的是:序列中每一个元素都必须在某一个子段内,任意两个子段不能有交集。

I/O格式

输入

输入的第一行是一个正整数\(T\),表示测试数据的组数。对于每组数据:
第一行是三个正整数\(N, K, S\),第二行是\(N\)个正整数\(a_1, a_2 \cdots a_N\)。

输出

每组数据输出一行。分别表示该组数据的划分方案数对\(10^5 + 3\)取模后的结果。

样例

输入

2
4 2 10
6 2 3 5
5 3 10
3 3 6 4 3

输出

2
3

样例说明

第一组数据中划分方案有2种:\(\{6\};\{2,3,5\}\)和\(\{6,2\};\{3,5\}\);
第二组数据中划分方案有3种:\(\{3\};\{3,6\};\{4,3\}\),\(\{3,3\};\{6\};\{4,3\}\)和\(\{3,3\};\{6,4\};\{3\}\)。

数据规模及约定

20%的数据:\(T \le 50, \quad N \le 15, \quad K = 4\)
另外20%的数据:\(T \le 20, \quad N \le 15, \quad K \le 6\)
另外30%的数据:\(T \le 10, \quad N \le 150, \quad K \le 10\)
另外30%的数据:\(T \le 10, \quad N \le 1.5 \times 10^4, \quad K \le 10\)
所有数据均满足:\(S \le 10^8,\quad \displaystyle\sum_{i=1}^{N} a_i \le K \times S\)
时间限制1s,空间限制256MB。

2019.1.31测验

未参加
状态
已结束
规则
OI
题目
3
开始于
2019-01-31 14:00
结束于
2019-01-31 17:30
持续时间
3.5 小时
主持人
参赛人数
29