统计难题

发布时间: 2018年1月29日 10:26   最后更新: 2018年2月11日 23:54   时间限制: 1000ms   内存限制: 128M

给定$n$个整数$a_1,a_2,…,a_n$。定义一个子区间$[l,r]$的价值为子区间内所有的数按位与的结果。即$f(l,r)=a_l \& a_{l+1} \& a_{l+2} \& … \& a_r$。请问所有子区间的价值之和是多少?即计算

$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l,r)$$

有多组测试数据(数据组数$≤20$)。对于每组数据,第一行有一个整数$n$。第二行有$n$个整数,中间以空格分割。
$1≤n≤10^5$
$1≤a_i≤10^6$

对于每组测试数据,输出一个整数表示所求得的答案。

复制
3
7 11 9
4
11 9 6 11
40
48

本题的输入数据量较大,建议使用高效的读写方式:C++使用scanf/printf代替cin/cout,Java使用BufferedReader/PrintWriter代替Scanner/System.out。

按位与运算可以在两个长度相同的二进制数上进行,即每一位做逻辑与运算。在C/C++和Java中的运算符为&。

对于第一个样例,答案的计算方式如下:

f(1, 1)+f(1, 2)+f(1, 3)+f(2, 2)+f(2, 3)+f(3, 3)=(7)+(7 & 11)+(7 & 11 & 9)+(11)+(11 & 9)+(9)=40

bitwise

Weekly Training 2018.1.28