第八届传智杯复赛第二场 题补bxg25-27 或许要期待明天
一、题意解释
子数组是类似字符串的子串，必须连续。题目要求求所有子数组的按位或的和。按位或就是把两个数二进制表示，对应的位进行或，只要有一个是1，那么就是1（只有全0才为0）。
二、思考思路
我们先考虑暴力，枚举所有的起点和终点，再枚举每一个数与他后面数的或，然后求和，时间复杂度来到了O(n^4)，不可取。按位或，我们能不能也按位来操作呢？如果我们对每个数的第i位进行操作，取得了这个位置的贡献，那一直累加到最高位不就成功了吗？ai最大为1e9，不到30位，那么时间复杂度是O(k*n)，其中k为最高位且不超过30。
对于或运算，只要有1那么左右包含这个数的子数组在这个位都有贡献，如果我们找1（第i个数第k位为1），会很麻烦，因为有1，它会在其他所有包含这个数的子数组中做贡献，而其他数在此位也为1（第j（j != i）个数的第k位也为1），那他俩都做贡献，而一个位在一个子数组只能贡献一次,我们难道还需要一直去重吗？这又要多少时间复杂度？这时候，想到：“正难则反”！
取1这么麻烦，那我们试试取0！只有这个子数组中第k位全部为0，第k位贡献才为0！
所以我们计算出所有第k位为0的子数组数量m，用全部子数组数量sum减去m，这就是所有k位有贡献的子数组的数量，再乘上2^k(2的k次幂)，就是k位的贡献。我们现在只需要计算出sum和每个m就能构造代码了。
计算sum和m的公式是类似的，当我们左起点选择l时，右终点只有n-l+1种选择（从l开始选到n）。也就是说：
- l = 1时，r = 1~n，共n种选择；
- l = 2时，r = 2~n，共n-1种选择；
- l = 3时，r = 3~n，共n-2种选择；
- ……
- l = n时，r = n，共1种选择；
综上，选择数是一个首相为n，公差为-1，末项为1的等差数列，所以sum = (n+1)*n / 2;
对于m， m = (len+1)*len / 2;
如此我们可以构造代码
三、代码
#include <bits/stdc++.h> #define int long long using namespace std; const int mod = 1e9 + 7; int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) { res = res*a % mod; } b >>= 1; a = a*a %mod; } return res; } signed main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; int n2 = qpow(2, mod-2); while (T--) { int n, ans = 0; cin >> n; vector<int> a(n, 0); for (int i = 0; i < n; i++) { cin >> a[i]; } int sum = n*(n+1) % mod * n2 % mod; for (int i = 0; i < 30; i++) { int len = 0, cnt = 0; for (int x : a) { if ((x >> i) & 1) { cnt = (cnt + len * (len+1) % mod * n2 % mod) % mod; len = 0; } else { len++; } } cnt = (cnt + len * (len+1) % mod * n2 % mod) % mod; int cnt1 = (sum - cnt + mod) % mod, w = 1 << i; ans = (ans + cnt1 * w % mod) % mod; } cout << ans << '\n'; } return 0; }其中n2代表的是2的逆元，可以直接用/2（除2）代替，1 << i是2^i(2的i次幂)。