← 返回题目列表

Codeforces · 2086/B

B. 大数组和段

中文机器翻译题面 查看原题

有一个数组 $$$a$$$ 由 $$$n$$$ 组成 积极 整数,以及正整数 $$$k$$$。根据以下规则从数组 $$$a$$$ 创建数组 $$$b$$$:

  • $$$b$$$ 包含 $$$n \cdot k$$$ 数字;
  • 数组$$$b$$$的前$$$n$$$个数与数组$$$a$$$的个数相同,即$$$b_{i} = a_{i}$$$ for $$$i \le n$$$;
  • 对于任何$$$i \gt 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$$$,使得 $$$[l, r]$$$ 段上数组 $$$b$$$ 的元素之和为 至少 $$$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$$$ 的数量。

示例

输入
复制

7
5 3 10
3 4 2 1 5
15 97623 1300111
105 95 108 111 118 101 95 118 97 108 111 114 97 110 116
1 100000 1234567891011
1
1 1 1
1
1 1 1
2
2 1 2
1 1
2 1 5
2 1

输出
复制

12
1452188
0
1
1
1
0

注意

在第一个测试用例中,数组 $$$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$$$。