题目机翻：有一次，Divan分析了一个由 n n n非负整数组成的序列 a 1 , a 2 , … , a n a_1, a_2, ldots, a_n a1,a2,…,an，如下所示。他考虑了序列 a a a的每个非空子序列，计算了其元素的位XOR，并将所有的XOR相加，得到了序列 a a a的惬意度。如果 c c c可以通过删除几个（可能是零或全部）元素从 d d d中得到，那么序列 c c c就是序列 d d d的子序列。例如， [ 1 , 2 , 3 , 4 ] [1, , 2, , 3, , 4] [1,2,3,4], [ 2 , 4 ] [2, , 4] [2,4]和 [ 2 ] [2] [2]是 [ 1 , 2 , 3 , 4 ] [1, , 2, , 3, , 4] [1,2,3,4]的子序列，但 [ 4 , 3 ] [4, , 3] [4,3]和 [ 0 ] [0] [0]不是。 Divan对他的分析非常自豪，但现在他失去了序列 a a a，还有舒适度值! 然而，迪凡记得序列 a a a的 m m m连续子段上的bitwise OR的值。事实证明，原始序列的每个元a素都至少包含在这 m m m段中的一个。Divan要求你利用他记忆中的信息帮助找到序列 a a a的舒适度。如果可能有几个舒适度值，请打印任何一个。由于结果可能非常大，请打印 1 0 9 + 7 10^9+7 109+7的模值。
思路分析：
假设存在以下数列：
A
1
=
a
0
m
…
a
0
i
…
a
03
a
02
a
01
a
00
A
2
=
a
1
m
…
a
1
i
…
a
13
a
12
a
11
a
10
A
3
=
a
2
m
…
a
2
i
…
a
23
a
22
a
21
a
20
…
A
n
=
a
n
m
…
a
n
i
…
a
n
3
a
n
2
a
n
1
a
n
0
A_1 = a_{0m} dots a_{0i} dots a_{03}a_{02}a_{01}a_{00}\ A_2 = a_{1m} dots a_{1i} dots a_{13}a_{12}a_{11}a_{10}\ A_3 = a_{2m} dots a_{2i} dots a_{23}a_{22}a_{21}a_{20}\ dots \ A_n = a_{nm} dots a_{ni} dots a_{n3}a_{n2}a_{n1}a_{n0}\
A1=a0m…a0i…a03a02a01a00A2=a1m…a1i…a13a12a11a10A3=a2m…a2i…a23a22a21a20…An=anm…ani…an3an2an1an0
对
30
30
30位而言，考虑每一位对答案的贡献：设
{
a
x
i
}
{a_{xi}}
{axi}位置有
y
y
y个
1
1
1，由于取奇数个
1
1
1异或才会产生有效值(
1
1
1)。因此最后在加和中所占的子和一定为：
s
u
b
s
u
m
=
2
i
×
2
n
−
x
×
(
2
x
−
2
x
−
1
)
=
2
i
×
2
n
−
1
subsum = 2^i times 2^{n - x} times (2^x - 2^{x - 1}) = 2^i times 2 ^ {n - 1}
subsum=2i×2n−x×(2x−2x−1)=2i×2n−1
那么将所有的数字或起来，然后对非零位计数求和即可。
也可以分位计数统计，最后累加答案。
Accepted Code#include#define int long long #define ll long long using namespace std; const int N = 2e5 + 10, mod = 1e9 + 7; int a[N]; int bit[40]; inline ll bin(ll x, ll n, ll MOD, ll ret = 1) { for (x %= MOD; n; n >>= 1, x = x * x % MOD) if (n & 1) ret = ret * x % MOD; return ret == 1 ? 0 : ret; } inline void solve(){ memset(bit, 0, sizeof(bit)); int n, m; cin >> n >> m; int res = bin(2, n - 1, mod), ans = 0; res = 1; for(int i = 1; i < n; i++) res = 2ll * res % mod; for (int i = 1, l, r, x; i <= m; i++) { cin >> l >> r >> x; for (int j = 0; j <= 30; j++) bit[j] |= x >> j & 1; } for (int i = 0; i <= 30; i++) if (bit[i]) ans = (ans + 1ll * res * (1ll << i) % mod) % mod; cout << ans << endl; } signed main(){ int t = 0; cin >> t; while(t--) solve(); return 0; }
