SP8059 AMR10E - Stocks Prediction

我的家人常去的一家百货商店想要预测每个月各种商品的销售量。库存过多费用高昂，而缺货又影响销售，因此需要找到平衡。作为销售顾问，经理找我帮忙。我设计了一个模型，用来预测每月的销售量 $S$ 是基于过去 $R$ 个月的销售情况。这个模型如下： $$ S(n) = a_1 \cdot S(n-1) + a_2 \cdot S(n-2) + \ldots + a_R \cdot S(n-R) $$ 其中 $S(n)$ 表示第 $n$ 个月的预测销售量（$n > R$），而 $S(1)$ 到 $S(R)$ 是给定的初始值。 经理对我的模型在帮助管理库存方面的表现感到满意。他希望我计算出每隔 $K$ 个月的销售额，并求出这些月中的前 $N$ 个的销售总和。例如，他可能想要未来 10 年中每年圣诞节月份（即 $N=10$ 和 $K=12$, 1 月为第一个月）的销售额总和，或者未来 2 年中每个季度末月份（即 $N=2$ 和 $K=3$）的销售额总和。 你能帮我写个程序来实现这些计算吗？

第一行是测试用例的数量 $T$。每个测试用例包含三行： - 第一行是三个整数 $N$、$R$、$K$。 - 第二行是 $R$ 个初始销售值 $S(1), S(2), \ldots, S(R)$。 - 第三行是 $R$ 个系数 $a_1, a_2, \ldots, a_R$，用于预测模型。

对于每个测试用例，输出经理要求的销售总和，并对 $1,000,000,007$ 取模。

- $1 \leq T \leq 40$ - $1 \leq N \leq 1000000000$ - $1 \leq R \leq 8$ - $1 \leq K \leq 8$ - $0 \leq \text{所有其他输入值} < 1000000007$ **样例输入** ``` 2 4 1 1 1 2 3 2 3 1 1 1 1 ``` **样例输出** ``` 15 44 ``` **样例解释** 在第一个测试用例中，$S(1)$ 为 1，且每月的销售量关系式为 $S(n) = 2 \cdot S(n-1)$。因为 $K$ 为 1，所以列表包括所有 $S$ 的项，结果就是前 4 项之和。 在第二个测试用例中，序列 $S$ 为斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34。挑选出的销售额为 2, 8, 34，它们的总和为 44。 **本翻译由 AI 自动生成**