题解

题面描述

给定一个长度为 $n$ 的正整数数组 $a$。我们定义一个数 $x$ 的 美丽值 如下：

• 如果将 $x$ 不停除以 $2$ 直到无法整除，此时得到的结果恰好为 $1$，则称 $x$ 是 美丽数，其美丽值为在过程中除以 $2$ 的次数。
• 否则，$x$ 不是美丽数，其美丽值记为 $0$。

题目要求计算数组 $a$ 中所有连续子数组（即区间）的和的美丽值之和。设某个子数组的和为 $S$，其贡献为 $f(S)$（若 $S=2^k$ 则 $f(S)=k$，否则 $f(S)=0$），要求求

题目内容

小苯认为一个数$x$是美丽数，当且仅当:如果将$x$不停除以$2$，直到$x$不整除$2$时停止，此时$x$恰好等于$1$。

如果一个数美丽，则其美丽值为:以上操作中除以$2$的次数。

否则一个数不美丽，则其美丽值为$0$。

现在小苯有一个长度为$n$的数组$a$，他想知道$a$中所有连续子数组的和的美丽值之和是多少，请你帮他算一算吧。

形式化的:记数字x的美丽值为$f(x)$则请你求出

$\sum_{t=1}^n$$\sum_{r=l}^n$$f(a_l+a_{l+1}+...+a_r)$

(其中$a_l+a_{l+1}+...a_r$表示$a$数组在$[l,r]$这一段区间的所有元素之和)

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下:

第一行输入一个正整数$n(1≤n≤3×10^5)$，表示数组$a$的长度。

第二行$n$个正整数$a_1a_2….a_n$$(0≤a_i<2^{30})$，表示数组$a$。

(保证同一个测试文件中的测试数据里，$n$的总和不超过$3×10^5$)

输出描述

对于每个测试数据，在单独的一行输出一个整数表示答案。

样例1

输入

2
5
2 4 4 3 5
4 
2 2 2 2

输出

15
13

说明

对于第二组测试数据:{$2,2,2,2$};

所有长度为$1$的子区间和都是美丽的，因为$2$的二进制中只有一个$1$，其美丽值为$1$，因此总美丽值为$1×4=4$;

所有长度为$2$的子区间和都是美丽的，因为他们的和都是$4$，$4$的美丽值为$2$，其总美丽值为$2×3=6$。

所有长度为$3$的子区间和都不是美丽的，因此美丽值总和为$0$。

唯一一个长度为$4$的子区间和是美丽的，其总和为$8$，美丽值为$3$

综上，所有区间的总美丽值之和为:$4+6+0+3=13$