← 返回题目列表

Codeforces · 2035/D

D. 又一个实数问题

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

给定一个长度为 $$$m$$$ 的数组 $$$b$$$。您可以执行以下操作任意次数(可能为零):

- 选择两个不同的索引 $$$i$$$ 和 $$$j$$$,其中 $$$\bf{1\le i < j\le m}$$$ 和 $$$b_i$$$ 是偶数,将 $$$b_i$$$ 除以 $$$2$$$,并将 $$$b_j$$$ 乘以 $$$2$$$。

由于这个问题太简单了,给你一个长度为$$$n$$$的数组$$$a$$$,需要针对$$$a$$$的每个前缀求解该问题。

换句话说,表示执行任意数量的$$$f(b)$$$等操作后$$$b$$$的最大总和,需要输出$$$f([a_1])$$$、$$$f([a_1,a_2])$$$、$$$\ldots$$$、 $$$f([a_1,a_2,\ldots,a_n])$$$ 分别对 $$$10^9+7$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的起始值。

保证所有测试用例的 $$$n$$$ 总和不会超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数,表示 $$$a$$$ 模 $$$10^9+7$$$ 的每个前缀的答案。

示例

输入 #1

3
10
1 2 3 4 5 6 7 8 9 10
11
1 6 9 4 7 4 4 10 3 2 3
4
527792568 502211460 850237282 374773208

输出 #1

1 3 8 13 46 59 126 149 1174 1311 
1 7 22 26 70 74 150 1303 1306 1308 1568 
527792568 83665723 399119771 773892979

注意

对于第一个示例中的每个前缀,操作后可能的数组为:

- $$$[1]$$$ 总和为 $$$1$$$;
- $$$[1, 2]$$$,总和为 $$$3$$$;
- $$$[1, 1, 6]$$$,总和为 $$$8$$$;
- $$$[1, 1, 3, 8]$$$,总和为 $$$13$$$;
- $$$[1, 1, 3, 1, 40]$$$,总和为 $$$46$$$;
- $$$[1, 1, 3, 1, 5, 48]$$$,总和为 $$$59$$$;
- $$$[1, 1, 3, 1, 5, 3, 112]$$$,总和为 $$$126$$$;
- $$$[1, 1, 3, 1, 5, 3, 7, 128]$$$,总和为 $$$149$$$;
- $$$[1, 1, 3, 1, 5, 3, 7, 1, 1152]$$$,总和为 $$$1174$$$;
- $$$[1, 1, 3, 1, 5, 3, 7, 1, 9, 1280]$$$,总和为 $$$1311$$$。