CF2086B Large Array and Segments

给定一个由 $n$ 个正整数组成的数组 $a$，以及一个正整数 $k$。根据以下规则从数组 $a$ 创建数组 $b$： - 数组 $b$ 包含 $n \cdot k$ 个元素； - 数组 $b$ 的前 $n$ 个元素与数组 $a$ 相同，即对于 $i \le n$，有 $b_{i} = a_{i}$； - 对于任意 $i > n$，有 $b_{i} = b_{i - n}$。 例如，若 $a = [2, 3, 1, 4]$ 且 $k = 3$，则 $b = [2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4]$。 给定一个数 $x$，要求统计满足以下条件的位置 $l$（$1 \le l \le n \cdot k$）的数量：存在位置 $r \ge l$，使得数组 $b$ 在区间 $[l, r]$ 上的元素之和不小于 $x$（即 $b_{l} + b_{l+1} + \dots + b_{r} \ge x$）。

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^{4}$）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$k$、$x$（$1 \le n, k \le 10^{5}$；$1 \le x \le 10^{18}$）。 第二行包含 $n$ 个整数 $a_{i}$（$1 \le a_{i} \le 10^{8}$）。 输入数据的额外限制： - 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^{5}$； - 所有测试用例的 $k$ 之和不超过 $2 \cdot 10^{5}$。

对于每个测试用例，输出一个整数——数组 $b$ 中满足条件的位置 $l$ 的数量。

在第一个测试用例中，数组 $b$ 如下所示： $$[3, 4, 2, 1, 5, 3, 4, 2, 1, 5, 3, 4, 2, 1, 5]$$ 共有 $12$ 个位置 $l$ 满足存在对应的位置 $r$。以下是其中部分（非全部）示例： - $l = 1$，存在 $r = 6$，区间 $[1, 6]$ 的和为 $18$； - $l = 2$，存在 $r = 5$，区间 $[2, 5]$ 的和为 $12$； - $l = 6$，存在 $r = 9$，区间 $[6, 9]$ 的和为 $10$。 翻译由 DeepSeek V3 完成