#P16113. [2026年山东集训一轮]做菜

    ID: 15324 传统题 3000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600动态规划计数DP组合数学排序

[2026年山东集训一轮]做菜

题目描述

有 nn 个顾客,每位顾客会点一道菜。做第 ii 道菜需要花费 aia_i 的时间,这位顾客吃完这道菜需要花费 bib_i 的时间。

你只能在同一个时刻做一道菜。对于每位顾客,一旦上菜,即对应的菜做完,他便开始吃,吃完之后就会离开。

给定一个整数 kk,你想选择服务其中的 kk 位顾客,并且可以按任意顺序服务,使得你的劳动时间最短。这里的“劳动时间”指从做第一道菜开始,到最后一位顾客吃完离开的时间。

现在给定 b1,b2,…,bnb_1,b_2,\ldots,b_n 和 kk。对于所有每个数都在 11 到 VV 之间的数列

a1,a2,…,ana_1,a_2,\ldots,a_n

一共有 VnV^n 个,求出最短劳动时间的总和。输出答案对 998244353998244353 取模的结果。

你需要回答 qq 组询问。每组询问的 bb 数组和 VV 都相同,只有 kk 可能不同。

输入格式

第一行三个整数 n,V,qn,V,q。

接下来一行 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n。

接下来一行 qq 个整数,表示各个询问的 kk。

输出格式

一共 qq 行,每行一个整数,表示答案。

样例 1 输入

2 2 2
1 2
1 2

样例 1 输出

10
16

样例 1 解释

当 k=1k=1 时,A=(1,1),(1,2),(2,1),(2,2)A=(1,1),(1,2),(2,1),(2,2) 的答案分别是 2,2,3,32,2,3,3。

当 k=2k=2 时,A=(1,1),(1,2),(2,1),(2,2)A=(1,1),(1,2),(2,1),(2,2) 的答案分别是 3,4,4,53,4,4,5。

样例 2 输入

3 5 3
1 2 4
1 2 3

样例 2 输出

448
787
1255

样例 3 输入

10 10 10
14 38 45 9 19 18 7 18 33 21
1 2 3 4 5 6 7 8 9 10

样例 3 输出

663655052
615617049
323725023
554911324
803518888
499232802
916051842
54293837
639852351
260050903

数据范围

对于所有数据,保证:

$$1\le n\le 30, \qquad 1\le V\le 20, \qquad 1\le b_i\le 600, \qquad 1\le q,k\le n.$$
子任务 nn VV 特殊性质 分数
1 ≤5\le 5 ≤3\le 3 无 10
2 ≤9\le 9 20
3 ≤30\le 30 ≤20\le 20 A 10
4 B
5 ≤3\le 3 无 20
6 ≤20\le 20 30

特殊性质:

  • A:保证 1≤k≤21\le k\le 2。
  • B:保证 n−1≤k≤nn-1\le k\le n。