题目描述

你有一个长度为 n 的数组 nums，其中所有元素都是非负整数。编写一个函数，找到满足以下条件的子数组 subarray 的数量：

subarray 中所有元素的二进制表示的所有位中，1 的数量总和是偶数。 例如，如果 nums = [2, 5, 6]：

• 数字 2 的二进制表示为 10，有 1 个 1；
• 数字 5 的二进制表示为 101，有 2 个 1；
• 数字 6 的二进制表示为 110，有 2 个 1。

在这个例子中，子数组 [5, 6] 和 [2, 5, 6] 满足条件，因为它们包含的数字的二进制中 1 的总数分别是 4 和 5，其中 4 是偶数。

测试案例

输入

3
1 2 3

输出

2

解释

对于案例，输入的数字3表示数组长度为3，依次输入1 2 3录入数组。 对于案例，输出符合条件的数组个数。

提示

• 你可以通过计算数组中每个元素的二进制中 1 的数量来开始解决这个问题。
• 考虑使用前缀和或类似方法来高效地处理子数组。
• 记住，你需要找到所有可能的子数组，这可能需要双重循环。