#P4750. 密码安全

    ID: 3870 传统题 2000ms 128MiB 尝试: 215 已通过: 98 难度: 6 上传者: 标签>难度分类提高组合数学贡献法排序与序列处理单调栈计算区间贡献位运算异或前缀和按位独立贡献一维前缀和CF2100鸣谢Tangjz提供试题

密码安全

题目描述

有些人在社交网络中使用过许多的密码,我们通过将各种形式的信息转化为 01 信号,再转化为整数,可以将这个人在一段时间内使用过的密码视为一个长度为 nn 的非负整数序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。一个人相邻几次在社交网络中使用的密码很有可能是类似的,这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响,我们需要计算上述序列的复杂程度。

对于区间 [L,R][L,R],定义

$$f(L,R)=\max(a_L,a_{L+1},\ldots,a_R),\qquad g(L,R)=a_L\oplus a_{L+1}\oplus\cdots\oplus a_R,$$

其中 ⊕\oplus 表示按位异或。求

∑L=1n∑R=Lnf(L,R)g(L,R)\sum_{L=1}^n\sum_{R=L}^n f(L,R)g(L,R)

对 109+6110^9+61 取模后的值。

输入格式

第一行包含一个正整数 TT,表示有 TT 组测试数据。 接下来依次给出每组测试数据。对于每组测试数据: 第一行包含一个正整数 nn。 第二行包含 nn 个非负整数,表示 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。 保证在一行中的每个整数之间有恰好一个空格,没有其他额外的空格。

输出格式

对于每组数据输出一行,包含一个整数,表示答案对 109+6110^9+61 取模的值。

样例 #1

样例输入 #1

3
1
61
5
1 2 3 4 5
5
10187 17517 24636 19706 18756

样例输出 #1

3721
148
821283048

数据规模与约定

对于 100%100\% 的数据,1≤T≤2001\le T\le 200,1≤n≤1051\le n\le 10^5,1≤∑n≤1061\le\sum n\le10^6,0≤ai≤1090\le a_i\le10^9。