← 返回题目列表

Codeforces · 2180/G

G. 平衡

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

你有一个数组 $$$a$$$ 最初是空的。您必须在阵列上处理以下类型的 $$$q$$$ 查询。

  • 类型 1:删除$$$a$$$的中间元素。形式上,如果 $$$a$$$ 具有 $$$n$$$ 元素,则删除 $$$a$$$ 的 $$$\lceil \frac{n}{2} \rceil$$$-th$$$^{\text{∗}}$$$ 元素并连接其余部分。每当您收到此类查询时,都保证 $$$a$$$ 不为空。
  • 类型 2:在 $$$a$$$ 的开头、结尾以及每两个连续元素之间插入 $$$x$$$。形式上,如果在该查询之前 $$$a = [a_1, a_2, \ldots, a_n]$$$,则在查询之后 $$$a$$$ 将变为 $$$[x, a_1, x, a_2, x, \ldots, x, a_n, x]$$$。
  • 类型 3:输出 余额 $$$a$$$的所有$$$2^L - 1$$$非空子序列$$$^{\text{†}}$$$的 ,其中$$$L$$$是此时$$$a$$$的长度。每当处理此查询时,保证 $$$L$$$ 不会是 $$$10^9 + 7$$$ 的倍数。

的 余额 数组 $$$b = [b_1, b_2, \ldots, b_m]$$$ 的 定义为 $$\text{balance}(b) = \frac{1 \cdot b_1 + 2 \cdot b_2 + \ldots + m \cdot b_m}{m}.$$

$$$^{\text{*}}$$$$$$\lceil k \rceil$$$ 是向上舍入的 $$$k$$$,i。 e.大于或等于 $$$k$$$ 的最小整数。

$$$^{\text{†}}$$$ 序列 $$$b$$$ 是序列 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$a$$$ 获得。如果两个子序列的集合被认为是不同的 职位 删除的元素的 不同。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$q$$$ ($$$2 \leq q \leq 10^6$$$),表示查询的数量。接下来的 $$$q$$$ 行描述了查询:

  • 类型 1 的每个查询的形式为 1,表示删除 $$$a$$$ 的中间元素。每当您收到此类查询时,都保证 $$$a$$$ 不为空。
  • 类型 2 的每个查询的形式为 2 x,其中 $$$x$$$ 是要按所述插入的整数,$$$1 \le x \le 10^9$$$。
  • 类型 3 的每个查询均采用以下形式 3,表示输出$$$a$$$所有非空子序列的余额之和。每当处理此查询时,保证 $$$a$$$ 的长度不会是 $$$10^9 + 7$$$ 的倍数。

还保证每个测试用例至少包含一个第三类查询,并且所有测试用例$$$q$$$的总和不超过$$$10^6$$$。

输出

对于类型 3 的每个查询,输出所需的余额总和。

正式地,令 $$$M = 10^9+7$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{P}{Q}$$$,其中 $$$P$$$ 和 $$$Q$$$ 是整数,$$$Q \not \equiv 0 \pmod{M}$$$。输出等于 $$$P \cdot Q^{-1} \bmod M$$$ 的整数。换句话说,输出这样一个整数 $$$x$$$ 使得 $$$0 \le x \lt M$$$ 和 $$$x \cdot Q \equiv P \pmod{M}$$$ 。

示例

输入
复制

2
5
2 1
2 2
3
1
3
10
2 33532
1
2 938556
2 559503
2 353115
3
1
3
1
3

输出
复制

833333355
7
856804480
553793656
724179701

注意

在第一个测试用例中,数组 $$$a$$$ 最初为空。

第一次查询后,数组变为$$$[1]$$$。

第二次查询后,数组变为$$$[2,\, 1,\, 2]$$$。

在第三个查询中,$$$a$$$ 的子序列及其余额如下:

  • 子序列 $$$[1]$$$ 余额 $$\frac{1 \cdot 1}{1} = 1;$$
  • 两个子序列 $$$[2]$$$,每个子序列都有余额 $$\frac{1 \cdot 2}{1} = 2;$$
  • 子序列 $$$[1,\,2]$$$ 余额 $$\frac{1 \cdot 1 + 2 \cdot 2}{2} = \frac{5}{2};$$
  • 子序列 $$$[2,\,1]$$$ 余额 $$\frac{1 \cdot 2 + 2 \cdot 1}{2} = 2;$$
  • 子序列 $$$[2,\,2]$$$ 余额 $$\frac{1 \cdot 2 + 2 \cdot 2}{2} = 3;$$
  • 子序列 $$$[2,\,1,\,2]$$$ 余额 $$\frac{1 \cdot 2 + 2 \cdot 1 + 3 \cdot 2}{3} = \frac{10}{3}.$$

因此,余额总和为:$$\frac{95}{6}.$$

第四次查询后,数组 $$$a$$$ 变为 $$$[2,\,2]$$$。