首页 > 试题广场 >

或许要期待明天

[编程题]或许要期待明天
  • 热度指数：41 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个长度为 n 的整数序列 \{a_1, a_2, \dots, a_n\}。
\hspace{15pt}你需要计算：这个序列的所有非空子数组的按位或（\operatorname{or}）之和。
\hspace{15pt}按位或的含义是：把两个整数写成二进制后逐位计算，只要某一位至少有一个是 1，结果这一位就是 1；否则结果这一位是 0。
\hspace{15pt}更具体地说，子数组 [l,r]（满足 1 \leqq l \leqq r \leqq n）对应的按位或为：

a_l \operatorname{or} a_{l+1} \operatorname{or} \dots \operatorname{or} a_r

\hspace{15pt}本题要求输出所有子数组的上述值加起来的总和。
\hspace{15pt}这里的子数组指从原序列中，连续选取一段元素组成的新序列，例如从 \{3,1,4,1,5\} 中选取 [2,4] 得到 \{1,4,1\}。本题只考虑非空子数组。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1 \leqq T \leqq 2 \times 10^5\right) 代表数据组数，每组测试数据描述如下：
\hspace{15pt}第一行输入一个整数 n\left(1 \leqq n \leqq 2 \times 10^5\right) 表示序列长度。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right) 表示序列元素。
\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 4 \times 10^5。


输出描述:
\hspace{15pt}对于每一组测试数据，新起一行输出一个整数，表示所有非空子数组的按位或之和对 10^9+7 取模后的结果。
示例1

输入

2
3
1 2 3
4
5 1 2 7

输出

15
51

说明

\hspace{15pt}对于第一组测试数据，所有非空子数组及其按位或为：
\hspace{23pt}\bullet\,子数组 [1,1]：按位或为 1；
\hspace{23pt}\bullet\,子数组 [2,2]：按位或为 2；
\hspace{23pt}\bullet\,子数组 [3,3]：按位或为 3；
\hspace{23pt}\bullet\,子数组 [1,2]：按位或为 1 \operatorname{or} 2 = 3；
\hspace{23pt}\bullet\,子数组 [2,3]：按位或为 2 \operatorname{or} 3 = 3；
\hspace{23pt}\bullet\,子数组 [1,3]：按位或为 1 \operatorname{or} 2 \operatorname{or} 3 = 3。
\hspace{15pt}把它们加起来得到 15。
\hspace{15pt}对于第二组测试数据，同理枚举所有非空子数组并计算按位或后求和，结果为 51。

备注:
\hspace{15pt}如果您选用 Python 作答本题，请注意：在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 4浏览

热门推荐

相关试题

或许要期待明天

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号