← 返回题目列表

Codeforces · 1582/B

B. Luntik 和子序列

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

Luntik 早上出来散步,发现了一个长度为 $$$n$$$ 的数组 $$$a$$$。他计算了数组元素的总和 $$$s$$$ ($$$s= \sum_{i=1}^{n} a_i$$$)。如果数组 $$$a$$$ 中的数字之和等于 $$$s-1$$$,则 Luntik 称该子序列几乎已满。

Luntik 确实想知道数组 $$$a$$$ 的几乎完整子序列的数量。但他需要回家,所以他请你解决这个问题!

如果 $$$x$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$y$$$ 获得,则序列 $$$x$$$ 是序列 $$$y$$$ 的子序列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来的 $$$2 \cdot t$$$ 行包含测试用例的描述。每个测试用例的描述由两行组成。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 60$$$) — 数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,打印数组中几乎完整的子序列的数量。

示例

输入 #1

5
5
1 2 3 4 5
2
1000 1000
2
1 0
5
3 0 2 1 1
5
2 1 0 3 0

输出 #1

1
0
2
4
4

注意

在第一个测试用例中,$$$s=1+2+3+4+5=15$$$,所有子序列中只有$$$(2,3,4,5)$$$是近满子序列,其中的总和等于$$$2+3+4+5=14=15-1$$$。

在第二个测试用例中,没有几乎完整的子序列。

在第三个测试用例中,$$$s=1+0=1$$$,几乎满的子序列是$$$(0)$$$ 和$$$()$$$(空子序列的总和是$$$0$$$)。